## Similar Problems

Similar Problems not available

# Merge Intervals

## Companies:

LeetCode: Merge Intervals Leetcode Solution

Difficulty: Unknown

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:

- Sort the given intervals based on the start element.
- Create an output list to store the merged intervals.
- Iterate over the intervals and check if the current interval overlaps with the previous interval.
- If the intervals overlap, merge them and update the end element of the merged interval.
- If the intervals do not overlap, add the current interval to the output list.
- 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.

## Solution Implementation

`1`