时间轴

2025-11-18

init

题目：

P57 插入区间

https://leetcode.cn/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150

先处理不能合并的，然后处理可以合并的，最后处理剩下的。
对于可以合并的有：

1
2
new_left = std::min(new_left, curr_left);
new_right = std::max(new_right, curr_right);

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	vector<vector<int> > insert(vector<vector<int> > &intervals, vector<int> &newInterval)
	{
		vector<vector<int> > res;
		int i, n = intervals.size();
		int curr_left, curr_right, new_left = newInterval[0], new_right = newInterval[1];
		for (i = 0; i < n; i++) {
			curr_left = intervals[i][0];
			curr_right = intervals[i][1];
			if (curr_right < new_left) {
				res.push_back({ curr_left, curr_right });
			} else {
				break;
			}
		}
		// 合并区间
		for (; i < n; i++) {
			curr_left = intervals[i][0];
			curr_right = intervals[i][1];
			if (curr_left <= new_right) {
				new_left = std::min(new_left, curr_left);
				new_right = std::max(new_right, curr_right);

			} else {
				break;
			}
		}
		res.push_back({ new_left, new_right });

		for (; i < n; i++) {
			curr_left = intervals[i][0];
			curr_right = intervals[i][1];
			res.push_back({ curr_left, curr_right });
		}
		return res;
	}
};