时间轴

2025-11-18

init

题目：

P56 合并区间

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

先按区间的左边界排序，再依次从左到右合并区间

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	vector<vector<int> > merge(vector<vector<int> > &intervals)
	{
		std::sort(intervals.begin(), intervals.end(),
			  [](vector<int> &vec1, vector<int> &vec2) { return vec1[0] < vec2[0]; });
		vector<vector<int> > res;
		vector<int> last;
		int left, right, last_left, last_right;
		for (vector<int> &interval : intervals) {
			left = interval[0];
			right = interval[1];
			if (last.empty()) {
				res.push_back({ left, right });
				last = res.back();
			} else {
				last_left = last[0];
				last_right = last[1];
				if (left <= last_right && right > last_right) {
					res.pop_back();
					res.push_back({ last_left, right });
					last = res.back();
				} else if (left <= last_right && right <= last_right) {
					continue;
				} else if (left > last_right) {
					res.push_back({ left, right });
					last = res.back();
				}
			}
		}
		return res;
	}
};