For this problem first, we sort all the intervals in increasing order of the starting values of intervals which will take O(N log N) time. We maintain a stack where we keep on checking the top most value of stack if the current iterated elenent is overlapping with the top most element of stack then we update our stack, if the interval is non-overlapping we just simply append it in our stack. Look the code below to get a better understanding of my approach and let me know if you face any problem while understanding the python 3 solution of the problem below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
#we need to sort the itnervals
intervals = sorted(intervals, key = lambda i : i[0])
n = len(intervals)
if n == 0:
return []
#stack to keep our final intervals
final_intervals = [intervals[0]]
#find overlapping intervals
for i in range(1,n):
curr_interval = intervals[i]
#check if the current interval is overlapping with the top most element of our stack
if final_intervals[-1][1] >= curr_interval[0]:
#they overlap
final_intervals[-1][1] = max(final_intervals[-1][1],curr_interval[1])
else:
final_intervals.append(curr_interval)
return final_intervals
|