57. Insert Interval

Posted on | In | 浏览 次
Words count in article: 730 | Reading time ≈ 3

题目

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].

解题思路

  • 这道题目给出一个有序的区间集合，再给出一个新的区间，将其合并进去区间集合中，然后输出合并后的区间集合
  • 这道题需要进行分类讨论，主要针对新的区间以及原区间集合的边界问题进行讨论。此处假设新的区间newInterval表现形式为[newStart, newEnd]，当前遍历到区间集合内的区间为[start, end]，此处需要注意的一点是区间集合内的区间都是已经排好序的，即当前区间end小于下一个区间的start。此处讨论主要分区间重叠的情况与不重叠两个方向进行讨论
    • 区间不重叠
      • 区间不重叠，说明新的区间无法与当前区间进行合并，因此我们只需要考虑是否将新的区间加入集合以及将当前区间加入的问题即可
      • newEnd < start
        • 此时说明新区间在当前区间的前面，但是我们需要判断新的区间是否已经加入区间集合中，如果已经加入，对新的区间无需任何操作，只需要加入当前区间即可，如果未加入，我们需要先加入新的区间（为了保证集合内区间也是排好序的），然后再加入当前区间
      • newStart > end
        • 无需考虑加入新区间问题，只需要把当前区间加入集合中即可
    • 区间重叠
      • 当前的区间与新的区间出现重叠的情况，区间可以进行合并。我们不需要考虑是否将区间加入到集合中，因为可能与后面区间仍然可能重叠而需要合并的情况，因此只需要更新一下新的区间，等到不重叠的情况时候再考虑加入，
        • newInterval.start = min(newInterval.start, intervals[i].start)
        • newInterval.end = max(newInterval.end, intervals[i].end)

实现代码

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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> v;
        if(intervals.size() == 0) {
            v.push_back(newInterval);
            return v;
        }

        bool isAdd = false;
        for(int i = 0; i < intervals.size(); ++i) { 
        
            if(intervals[i].start > newInterval.end) {
                if(!isAdd) v.push_back(newInterval);
                v.push_back(intervals[i]);
                isAdd = true;
            }
            else if(intervals[i].end < newInterval.start) {
                v.push_back(intervals[i]);
            }
            else {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            }
        }
        if(!isAdd) v.push_back(newInterval);
        return v;
    }
};