LeetCode 0057 - Insert Interval
# Hints
- 水题
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
# 题意
给定 个按左端点升序排列的闭区间 ,给定一个新区间 ,要求将新区间插入这些区间中,然后将所有的相交的区间进行合并。
# 题解
本题和 LeetCode 0056 几乎没有区别,不知道为什么要设为 Hard 难度。
# AC代码
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>> & intervals, vector<int> & newInterval) {
// 预处理
auto cmp = [](const vector<int> & A, const vector<int> & B) {
return (A[0] < B[0]);
};
auto it = lower_bound(intervals.begin(), intervals.end(), newInterval, cmp);
intervals.insert(it, newInterval);
// 求解
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