LeetCode 0056 - Merge Intervals
# Hints
- 水题
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
# 题意
给定 个闭区间 ,要求将所有的相交的区间进行合并,返回合并后的所有区间。
# 题解
水题,将区间按左端点从小到大排序,然后从左到右依次遍历进行合并即可。
细节问题:
- 注意特判 的情况。
# AC代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>> & intervals) {
// 特判
if (intervals.empty()) {
return vector<vector<int>>();
}
// 排序
auto cmp = [](const vector<int> & A, const vector<int> & B) {
return (A[0] < B[0]);
};
sort(intervals.begin(), intervals.end(), cmp);
// 求解
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i ++) {
if (is_crossed(res.back(), intervals[i])) {
res.back()[1] = max(res.back()[1], intervals[i][1]);
} else {
res.push_back(intervals[i]);
}
}
// 返回
return res;
}
// 判断区间是否相交
inline bool is_crossed(const vector<int> & lhs, const vector<int> & rhs) {
return (lhs[1] >= rhs[0]);
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01