diff options
Diffstat (limited to 'merge_intervals.py')
-rw-r--r-- | merge_intervals.py | 28 |
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]])) |