[LeetCode] Insert Interval

Insert Interval

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

Solution:
Any two intervals a, b have three relations:
1) a lies to the left of b.
2) a overlaps with b.
3) a lies to the right of b.
The following method scans all intervals satisfying 1) and 2).
Alternatively, one may do binary search to locate one interval satisfying 2), then scan left and right, respectively.
Time Complexity:
Suppose there are n intervals in total, and the number of intervals satisfying 1), 2) and 3) are n1, n2, and n3, respectively. Then the following code takes O(n1 + n2) time. Alternatively, by using binary search, it takes O(n2 + log (n1 + n3)) time.

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

/** * 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 { private Interval merge(Interval a, Interval b) { int start = Math.min(a.start, b.start); int end = Math.max(a.end, b.end); return new Interval(start, end); } private boolean overlap(Interval a, Interval b) { if (a.end < b.start || b.end < a.start) { return false; } return true; } private boolean toTheRight(Interval a, Interval b) { return (b.end < a.start); } public List<Interval> insert( List<Interval> intervals, Interval newInterval ) { int i = 0; while ( i < intervals.size() && toTheRight(newInterval, intervals.get(i)) ) { i++; } while ( i < intervals.size() && overlap(newInterval, intervals.get(i)) ) { newInterval = merge(newInterval, intervals.remove(i)); } intervals.add(i, newInterval); return intervals; } }