LeetCode: 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: 
Below is a simple solution in Python:

view plainprint?

1. # Definition for an interval.  
2. # class Interval:  
3. #     def __init__(self, s=0, e=0):  
4. #         self.start = s  
5. #         self.end = e  
6.   
7. class Solution:  
8.   
9.     def insert(self, intervals, newInterval):  
10.         l = []  
11.         count = 0  
12.         while(count < len(intervals)):  
13.             if(newInterval.start <= intervals[count].end):  
14.                 if(newInterval.end >= intervals[count].start):  
15.                     newInterval.start = min(intervals[count].start, newInterval.start)  
16.                 break  
17.             l.append(intervals[count])  
18.             count += 1  
19.         l.append(newInterval)  
20.         while(count < len(intervals)):  
21.             if(newInterval.end < intervals[count].start):  
22.                 break  
23.             l[-1].end = max(intervals[count].end, l[-1].end)  
24.             count += 1  
25.         while(count < len(intervals)):  
26.             l.append(intervals[count])  
27.             count += 1  
28.         return l  

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:

    def insert(self, intervals, newInterval):
        l = []
        count = 0
        while(count < len(intervals)):
            if(newInterval.start <= intervals[count].end):
                if(newInterval.end >= intervals[count].start):
                    newInterval.start = min(intervals[count].start, newInterval.start)
                break
            l.append(intervals[count])
            count += 1
        l.append(newInterval)
        while(count < len(intervals)):
            if(newInterval.end < intervals[count].start):
                break
            l[-1].end = max(intervals[count].end, l[-1].end)
            count += 1
        while(count < len(intervals)):
            l.append(intervals[count])
            count += 1
        return l

And here is a faster solution using binary search:

view plainprint?

1. class Solution:    
2.     
3.     def insert(self, intervals, newInterval):    
4.         if len(intervals) == 0:    
5.             return [newInterval]    
6.                 
7.         v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)    
8.         v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)    
9.      
10.         if (v1 & 1):    
11.             newInterval.start = intervals[v1>>1].start     
12.         if (v2 & 1):    
13.             newInterval.end = intervals[(v2)>>1].end   
14.                     
15.         return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:]   
16.             
17.     def search(self, intervals, index, start=0, end=0, isStart=0):    
18.         while(start <= end):    
19.             middle = (end+start)>>1   
20.             if intervals[middle].start <= index and intervals[middle].end >= index:    
21.                 return (middle << 1)+1   
22.             if intervals[middle].start > index:    
23.                 end = middle - 1  
24.             else:  
25.                 start = middle + 1         
26.         return start << 1  

class Solution:  
  
    def insert(self, intervals, newInterval):  
        if len(intervals) == 0:  
            return [newInterval]  
              
        v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)  
        v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)  
   
        if (v1 & 1):  
            newInterval.start = intervals[v1>>1].start   
        if (v2 & 1):  
            newInterval.end = intervals[(v2)>>1].end 
                  
        return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:] 
          
    def search(self, intervals, index, start=0, end=0, isStart=0):  
        while(start <= end):  
            middle = (end+start)>>1 
            if intervals[middle].start <= index and intervals[middle].end >= index:  
                return (middle << 1)+1 
            if intervals[middle].start > index:  
                end = middle - 1
            else:
                start = middle + 1       
        return start << 1

Third solution:

view plainprint?

1. class Solution:   
2.     
3.     def insert(self, intervals, newInterval):  
4.         s, e = newInterval.start, newInterval.end  
5.         left = [i for i in intervals if i.end < s]  
6.         right = [i for i in intervals if i.start > e]  
7.         if left + right != intervals:  
8.             s = min(s, intervals[len(left)].start)  
9.             e = max(e, intervals[~len(right)].end)  
10.         return left + [Interval(s, e)] + right  

class Solution: 
  
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right

If you want to train the code reading skills, here is another approach in Java:

view plainprint?

1. /** 
2.  * Definition for an interval. 
3.  **/  
4. class Interval {  
5.     int start;  
6.     int end;  
7.     Interval() { start = 0; end = 0; }  
8.     Interval(int s, int e) { start = s; end = e; }  
9. }  
10.   
11. public class Solution {  
12.     public List<Interval> insert(List<Interval> intervals, Interval newInterval){  
13.         List<Interval> is = new ArrayList<Interval>();  
14.         if(intervals == null || newInterval == null) return is;  
15.   
16.         int status = 0;  
17.         Interval open = null;  
18.         for(Interval i: intervals){  
19.   
20.             //if not found a interval containing the newInterval  
21.             if(status==0){  
22.                 if(i.start > newInterval.end){  
23.                     is.add(newInterval);  
24.                     is.add(i);  
25.                     status = 2;  
26.                 }else if(i.end < newInterval.start){  
27.                     is.add(i);  
28.                 }else if(i.start<= newInterval.start && i.end < newInterval.end){  
29.                     open = new Interval(i.start, newInterval.end);  
30.                     status = 1;  
31.                 }else if(i.start > newInterval.start && i.end < newInterval.end){  
32.                     status = 1;  
33.                     open = new Interval(newInterval.start, newInterval.end);  
34.                 }else {  
35.                     is.add(new Interval(Math.min(newInterval.start, i.start), i.end));  
36.                     status = 2;  
37.                 }  
38.             }else if(status == 1){  
39.                 if(i.start <= newInterval.end && i.end>= newInterval.end){  
40.                     status = 2;  
41.                     open.end = i.end;  
42.                     is.add(open);  
43.                 }else if(i.start > newInterval.end){  
44.                     status = 2;  
45.                     open.end = newInterval.end;  
46.                     is.add(open);  
47.                     is.add(i);  
48.                 }                  
49.             }else {   //status = 2  
50.                 is.add(i);  
51.             }  
52.         }  
53.   
54.         if(status == 0) is.add(newInterval);  
55.         if(status == 1){  
56.             open.end = newInterval.end;  
57.             is.add(open);  
58.         }  
59.         return is;  
60.     }  
61. }  

/**
 * Definition for an interval.
 **/
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){
        List<Interval> is = new ArrayList<Interval>();
        if(intervals == null || newInterval == null) return is;

        int status = 0;
        Interval open = null;
        for(Interval i: intervals){

            //if not found a interval containing the newInterval
            if(status==0){
                if(i.start > newInterval.end){
                    is.add(newInterval);
                    is.add(i);
                    status = 2;
                }else if(i.end < newInterval.start){
                    is.add(i);
                }else if(i.start<= newInterval.start && i.end < newInterval.end){
                    open = new Interval(i.start, newInterval.end);
                    status = 1;
                }else if(i.start > newInterval.start && i.end < newInterval.end){
                    status = 1;
                    open = new Interval(newInterval.start, newInterval.end);
                }else {
                    is.add(new Interval(Math.min(newInterval.start, i.start), i.end));
                    status = 2;
                }
            }else if(status == 1){
                if(i.start <= newInterval.end && i.end>= newInterval.end){
                    status = 2;
                    open.end = i.end;
                    is.add(open);
                }else if(i.start > newInterval.end){
                    status = 2;
                    open.end = newInterval.end;
                    is.add(open);
                    is.add(i);
                }                
            }else {   //status = 2
                is.add(i);
            }
        }

        if(status == 0) is.add(newInterval);
        if(status == 1){
            open.end = newInterval.end;
            is.add(open);
        }
        return is;
    }
}