1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 14, 2014
4+ Problem: Insert Interval
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/insert-interval/
7+ Notes:
8+ Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
9+ You may assume that the intervals were initially sorted according to their start times.
10+ Example 1:
11+ Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
12+ Example 2:
13+ Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
14+ This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
15+
16+ Solution: For example 2:
17+ 1. compare [1,2] with [4,9], then insert [1,2];
18+ 2. merge [3,5] with [4,9], get newInterval = [3,9];
19+ 3. merge [6,7] with [3,9], get newInterval = [3,9];
20+ 4. merge [8,10] with [3,9], get newInterval = [3,10];
21+ 5. compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...
22+ Solution 1 : Time O(N).
23+ Solution 2 : Time O(Log(N)).
24+ */
25+
26+ /**
27+ * Definition for an interval.
28+ * public class Interval {
29+ * int start;
30+ * int end;
31+ * Interval() { start = 0; end = 0; }
32+ * Interval(int s, int e) { start = s; end = e; }
33+ * }
34+ */
35+ public class Solution {
36+ public List <Interval >insert_1 (List <Interval >intervals ,Interval newInterval ) {
37+ List <Interval >res =new ArrayList <Interval >();
38+ boolean inserted =false ;
39+ for (Interval it :intervals ) {
40+ if (inserted ||it .end <newInterval .start ) {
41+ res .add (it );
42+ }else if (it .start >newInterval .end ) {
43+ res .add (newInterval );
44+ res .add (it );
45+ inserted =true ;
46+ }else {
47+ newInterval .start =Math .min (newInterval .start ,it .start );
48+ newInterval .end =Math .max (newInterval .end ,it .end );
49+ }
50+ }
51+ if (inserted ==false )res .add (newInterval );
52+ return res ;
53+ }
54+ public List <Interval >insert (List <Interval >intervals ,Interval newInterval ) {
55+ List <Interval >res =new ArrayList <Interval >();
56+ int n =intervals .size ();
57+ int left =0 ,right =n -1 ;
58+ while (left <=right ) {
59+ int mid =left + (right -left ) /2 ;
60+ if (intervals .get (mid ).start >newInterval .start )right =mid -1 ;
61+ else left =mid +1 ;
62+ }
63+ int idxStart =right ;
64+ left =0 ;right =n -1 ;
65+ while (left <=right ) {
66+ int mid =left + (right -left ) /2 ;
67+ if (intervals .get (mid ).end <newInterval .end )left =mid +1 ;
68+ else right =mid -1 ;
69+ }
70+ int idxEnd =left ;
71+ if (idxStart >=0 &&newInterval .start <=intervals .get (idxStart ).end ) {
72+ newInterval .start =intervals .get (idxStart --).start ;
73+ }
74+ if (idxEnd <n &&newInterval .end >=intervals .get (idxEnd ).start ) {
75+ newInterval .end =intervals .get (idxEnd ++).end ;
76+ }
77+ for (int i =0 ;i <=idxStart ; ++i ) {
78+ res .add (intervals .get (i ));
79+ }
80+ res .add (newInterval );
81+ for (int i =idxEnd ;i <n ; ++i ) {
82+ res .add (intervals .get (i ));
83+ }
84+ return res ;
85+ }
86+ }
