57, same with problem 56

chaor · chaor · commit 68c8c7cbfe8c · 2016-03-21T23:17:50.000-07:00
diff --git a/57_Insert_Interval.py b/57_Insert_Interval.py
@@ -1,28 +1,22 @@
-# 2015-06-17  Runtime: 84 ms
+# 2016-03-21  151 tests, 108 ms
 
 # Definition for an interval.
-# class Interval:
+# class Interval(object):
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
-class Solution:
-    # @param {Interval[]} intervals
-    # @param {Interval} newInterval
-    # @return {Interval[]}
+class Solution(object):
     def insert(self, intervals, newInterval):
-        result, i = [], 0
-        # add all intervals ending before newInterval starts
-        while i < len(intervals) and intervals[i].end < newInterval.start:
-            result.append(intervals[i])
-            i += 1
-        # merge all overlapping intervals to one considering newInterval
-        while i < len(intervals) and intervals[i].start <= newInterval.end:
-            newInterval.start, newInterval.end = min(newInterval.start, intervals[i].start), max(newInterval.end, intervals[i].end)
-            i += 1
-        result.append(newInterval) # add the union of intervals we got
-        # add all the rest
-        while i < len(intervals): 
-            result.append(intervals[i])
-            i += 1
-        return result
+        """
+        :type intervals: List[Interval]
+        :type newInterval: Interval
+        :rtype: List[Interval]
+        """
+        result, overlap, begin = [], 0, float('-inf')
+        for x, y in sorted([(i.start, 1) for i in intervals] + [(i.end, -1) for i in intervals] +
+                [(newInterval.start, 1), (newInterval.end, -1)], key = lambda x:(x[0], -x[1])):
+            if y == 1 and not overlap: begin = x
+            if y == -1 and overlap == 1: result += Interval(begin, x),
+            overlap += y
+        return result
