L1-插入区间

Posted on | In |

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

样例
Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].

Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package Sort;
import java.util.ArrayList;
  class Interval {
     int start, end;
     Interval(int start, int end) {
          this.start = start;
          this.end = end;
  }
  }

class Solution {
    /**
     * Insert newInterval into intervals.
     * @param intervals: Sorted interval list.
     * @param newInterval: A new interval.
     * @return: A new sorted interval list.
     */
	
public static void main(String[] args)
{
	ArrayList<Interval> list=new ArrayList<Interval>();
	list.add(new Interval(1,2));
	list.add(new Interval(4,6));
	ArrayList<Interval> newlist=insert(list,new Interval(3,5));
	for(Interval interval:newlist)
	{
	System.out.println(interval.start+"   "+interval.end);	
	}
}
private static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> result = new ArrayList<Interval>();
    if (intervals == null || intervals.isEmpty()) {
        if (newInterval != null) {
            result.add(newInterval);
        }
        return result;
    }

    int insertPos = 0;
    for (Interval interval : intervals) {
        if (newInterval.end < interval.start) {
            // case 1: [new], [old]
            result.add(interval);
        } else if (interval.end < newInterval.start) {
            // case 2: [old], [new]
            result.add(interval);
            insertPos++;
        } else {
            // case 3, 4: [old, new] or [new, old]
            newInterval.start = Math.min(newInterval.start, interval.start);
            newInterval.end = Math.max(newInterval.end, interval.end);
        }
    }

    result.add(insertPos, newInterval);

    return result;
}
}

有四种情况，
遍历intervals的interval

  • [N][I] <==>newInterval.end<interval.start,直接插入就好
  • [I], [N] <==>newInterval.start>interval.end,记录插入的位置,newInterval有可能在此处插入，也有可能在其后面的间隔插入。故遍历时需要在这种情况下做一些标记以确定最终插入位置。
  • [NI] <==> newInterval.end == interval.start，这种情况下需要进行合并操作。
  • [IN] <==> newInterval.start == interval.end, 这种情况下也需要进行合并.

难点在于产生了新的间隔，且这种情况一旦发生，原来的newInterval即被新的合并间隔取代，这是一个非常关键的突破口。