56, mix all starts and all ends then sort, check overlap

chaor · chaor · commit 2a0db5940b9c · 2016-03-21T22:39:30.000-07:00
diff --git a/56_Merge_Intervals.py b/56_Merge_Intervals.py
@@ -1,21 +1,20 @@
-# 2015-06-17  Runtime: 102 ms
+# 2016-03-21   168 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
-    # @return {Interval[]}
+class Solution(object):
     def merge(self, intervals):
-        if len(intervals) == 0: return []
-        intervals.sort(key = lambda x: x.start)
-        result = [intervals[0]]
-        for i in intervals:
-            if i.start > result[-1].end:
-                result.append(i)
-            else:
-                result[-1].end = max(result[-1].end, i.end)
-        return result
+        """
+        :type intervals: List[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], 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
