Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals =[[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]

Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals =[[4,7],[1,4]] Output:[[1,7]] Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Brainstorming

so the idea is similar to what we did in [[Insert intervals]] but with minimised complexity , instead of worrying about the past interval or keeping a track of where are we currently . The only complexity that got added is the intervals are not sorted so we would need to that once we have done it the problem is pretty simple

1. sort the intervals in ascending order based on the start_index
2. create a new list to hold the merged intervals
3. add the first entry from our intervals list to this new merged_intervals
4. now iterate through the remaining list
   1. at any given point we will check for overlap of the current interval and the last interval that is added to the merge_intervals
      1. There are only two possibilities: 1.Case A: No Overlap. The current_interval starts after the last_merged_interval ends. (e.g., comparing [9, 11] to [2, 4]). This means a new, separate busy block has started. Action: Add the current_interval as a new entry to your merged_list. Case B: Overlap! The current_interval starts before or at the same time as the last_merged_interval ends. (e.g., comparing [10, 12] to the last block, which is now [9, 11]). This means the current busy block is longer than you thought.Action: Do NOT add a new entry. Instead, update the end time of the last_merged_interval to be the max of the two end times.

below is the python implementation

 intervals =[[4,7],[1,4]]
 
 intervals.sort(key=lambda x:x[0])
 
 merge_intervals = []
 merge_intervals.append(intervals[0])
 
 for i in range(1, len(intervals)):
	 if intervals[i][0] <= merge_intervals[-1][1]:
		 merge_intervals[-1][1] = max(intervals[i][1], merge_intervals[-1][1])
	 else:
		 merge_intervals.append(intervals[i])

print(merge_intervals)