leetcode 57 Insert Interval
z
 2018-08-12 15:40:32  

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:

1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3
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].
  • 若interval在当前区间的右边，将当前区间添加到ans中
  • 若interval在当前区间的左边，判断是否已经插入过interval
    • 若没插入过interval，插入interval，修改插入标记，插入当前区域
    • 若已插入过interval，插入当前区域
  • 若interval和当前区间有交集，将interval.start 取interval和当前区间的最小值，interval.end 取interval和当前区域的最大值，继续循环。
  • 循环结束，判断是否已经插入，若没插入，即将interval插入ans，结束。
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

class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int start = newInterval.start;
        int end = newInterval.end;
        List<Interval> ans = new LinkedList<Interval>();
        int n = intervals.size();
        if (n == 0){
            ans.add(newInterval);
        }
        else{
            boolean inserted = false;
            for (Interval s: intervals){
                if (end < s.start){
                    if (! inserted){
                        ans.add(new Interval(start, end));
                        inserted = true;
                    }
                    ans.add(s);
                }
                else if (start > s.end){
                    ans.add(s);
                }
                else{
                    start = Math.min(s.start, start);
                    end = Math.max(s.end, end);
                }
            }
            if (!inserted){
                ans.add(new Interval(start, end));
            }
        }
        return ans;
    }
}