Merge Intervals - Leetcode Solution

Problem statement: Given a list of intervals, merge overlapping intervals and return the merged intervals in sorted order.

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, they are merged into [1,6].

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

Solution: The problem can be solved using a simple approach of merging intervals which are present next to each other. Here is the high-level algorithm for the problem:

1. Sort the given intervals based on the start element.
2. Create an output list to store the merged intervals.
3. Iterate over the intervals and check if the current interval overlaps with the previous interval.
4. If the intervals overlap, merge them and update the end element of the merged interval.
5. If the intervals do not overlap, add the current interval to the output list.
6. Return the output list.

Let's implement the above algorithm in Python:

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: # Sort the given intervals based on the start element. intervals = sorted(intervals, key=lambda x: x[0]) # Create an output list to store the merged intervals. merged_intervals = [] prev_interval = intervals[0] # Iterate over the intervals and merge the overlapping intervals. for i in range(1, len(intervals)): current_interval = intervals[i] if prev_interval[1] >= current_interval[0]: # Merge the current interval with the previous interval. prev_interval[1] = max(prev_interval[1], current_interval[1]) else: # Add the previous interval to the merged intervals list. merged_intervals.append(prev_interval) prev_interval = current_interval # Add the last interval to the merged intervals list. merged_intervals.append(prev_interval) return merged_intervals

Complexity analysis: Time complexity: The algorithm runs in O(nlogn) time, where n is the number of intervals. This is because the given intervals are sorted in O(nlogn) time, and the merging process takes place in linear time. Space complexity: The algorithm runs in O(n) space because we need to store the merged intervals list in the worst case.

1