aboutsummaryrefslogtreecommitdiff
path: root/merge_intervals.py
diff options
context:
space:
mode:
Diffstat (limited to 'merge_intervals.py')
-rw-r--r--merge_intervals.py28
1 files changed, 28 insertions, 0 deletions
diff --git a/merge_intervals.py b/merge_intervals.py
new file mode 100644
index 0000000..74c64a6
--- /dev/null
+++ b/merge_intervals.py
@@ -0,0 +1,28 @@
+# 56. Merge Intervals
+
+"""
+given an array of 'intervals' where 'intervals[i] = [start_i, end_i]', merge
+all overlapping intervals, and return an array of the non-overlapping
+intervals that cover all the intervals in the input.
+"""
+
+
+class Solution(object):
+ def merge(self, intervals):
+ """
+ :type intervals: List[List[int]]
+ :rtype: List[List[int]]
+ """
+ stack = []
+ for i in sorted(intervals, key=lambda i: i[0]):
+ if stack and i[0] <= stack[-1][1]:
+ stack[-1][1] = max(stack[-1][1], i[1])
+ else:
+ stack += [i]
+ return stack
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.merge(intervals=[[1, 3], [2, 6], [8, 10], [15, 18]]))
+ print(obj.merge(intervals=[[1, 4], [4, 5]]))