Merge Intervals

Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key =lambda x: x[0])
        merged =[]
        for i in intervals:
			# if the list of merged intervals is empty 
			# or if the current interval does not overlap with the previous,
			# simply append it.
            if not merged or merged[-1][-1] < i[0]:
                merged.append(i)
			# otherwise, there is overlap,
			#so we merge the current and previous intervals.
            else:
                merged[-1][-1] = max(merged[-1][-1], i[-1])
        return merged

Attempt 1

• gyan_pelo

• intervals are about sorting based on the first or the starting time, here overlapping intervals can be checked by using a Min heap, something similar to maximum number of rooms required problem. So if the starting time of previous interval is more than the ending time of next one then merge them. How to merge? Remove last element of first and first element of second interval, now the array size will change will it cause any issues?

• Final approach, loop through the array, push elements in min heap

• pseudo_code

• dry_run

Links

• https://leetcode.com/problems/merge-intervals/