Insert Interval/ Merge Intervals

发表于

Insert Interval

Question

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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Analysis

设newInterval的起止为low和high

  • 对于集合中所有end小于low的区间直接加入res中
  • 集合中start小于等于low的属于可以归并的区间，则一直循环下去并始终取最小为下届，最大为上届(newInterval的)，直到start>low，将最终的 newInterval加入res
  • 剩余的区间直接加入res

Code

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int num=intervals.size();
        int i=0;
        List<Interval> res=new LinkedList();
        while(i<num&&intervals.get(i).end<newInterval.start){
            res.add(intervals.get(i));
            i++;
        }
        while(i<num&&intervals.get(i).start<=newInterval.end){
            int start=Math.min(intervals.get(i).start,newInterval.start);
            int end=Math.max(intervals.get(i).end,newInterval.end);
            newInterval=new Interval(start,end);
            i++;
        }
        res.add(newInterval);
        while(i<num){
            res.add(intervals.get(i));
            i++;
        }
        return res;
    }
}

Merge Intervals

Question

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Analysis

重点是要对现有的序列以start从小到大排序

将第一个区间的上下界设为low,high，分为两种情况：

  • high<当前区间的start，代表无重合部分，直接将区间[low,high]加入res，并且以当前区间的上下界更新low,high
  • high≥当前区间的start，区间有重合，取两者较大的上界为high，继续对比

Code

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
39
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size()==0||intervals.size()==1)
            return intervals;
        Collections.sort(intervals, new Comparator<Interval>() {
        @Override
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        });
        
        int low=intervals.get(0).start;
        int high=intervals.get(0).end;
        int i=0;
        List<Interval> res=new LinkedList<>();
        while(i<intervals.size()){
             if(high<intervals.get(i).start){
                 res.add(new Interval(low,high));
                 low=intervals.get(i).start;
                 high=intervals.get(i).end;
             }
             else{
                 high=Math.max(high,intervals.get(i).end);
             }
             i++;
        }
        res.add(new Interval(low,high));
        return res;
    }
}