# Merge Intervals

##### December 21, 2023

## Problem #

Given a list of intervals (each interval represented by a pair of integers), merge overlapping intervals and return the result in sorted order.

## Solution #

The Python function `merge_intervals`

successfully merges overlapping intervals and returns the result in sorted order. Here’s the code:

```
def merge_intervals(intervals):
"""
Merge overlapping intervals and return the result in sorted order.
:param intervals: A list of intervals, each represented as a pair of integers
:return: A list of merged intervals in sorted order
"""
# Sort the intervals based on the starting value of each interval
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# If the list of merged intervals is empty or if the current interval does not overlap with the previous
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# Otherwise, there is an overlap, so we merge the current and previous intervals
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
# Example usage
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
merged_intervals = merge_intervals(intervals)
print(merged_intervals)
```

This code works as follows:

- First, it sorts the intervals based on the starting value of each interval.
- Then, it iterates through the sorted intervals. For each interval, it checks if it overlaps with the last interval in the
`merged`

list. - If there’s no overlap, the interval is added to
`merged`

. If there is an overlap, it merges the current interval with the last one in`merged`

by updating the end value of the last interval in`merged`

to be the maximum of its own end and the end of the current interval. - The resulting
`merged`

list contains the merged intervals in sorted order.

In the provided example, intervals `[[1, 3], [2, 6], [8, 10], [15, 18]]`

are merged into `[[1, 6], [8, 10], [15, 18]]`

.

## Solution analysis #

The algorithm used in the provided code for merging intervals is a combination of **sorting** and a **linear scan**. This approach is commonly used in interval problems and is known for its efficiency and simplicity. Here’s how it works:

### Sorting #

**Initial Step**: The algorithm starts by sorting the list of intervals based on their starting points. This is crucial because it arranges the intervals in a sequence where checking for overlaps becomes straightforward.**Sorting Criterion**: The key for sorting is the starting point of each interval (`lambda x: x[0]`

), ensuring that intervals with lower start points come first.

### Linear Scan #

**One Pass Through Sorted Intervals**: After sorting, the algorithm makes a single pass through the sorted intervals.**Merging Logic**:**No Overlap**: If the current interval (`interval`

) does not overlap with the last interval in the`merged`

list, it is added to`merged`

. This is determined by checking if the start of the current interval is greater than the end of the last interval in`merged`

.**Overlap**: If there is an overlap, the algorithm merges the current interval with the last interval in`merged`

. This is done by updating the end of the last interval in`merged`

to the maximum end value between the two overlapping intervals.

### Efficiency #

**Time Complexity**: The time complexity of this algorithm is dominated by the sorting step, which is typically O(n log n) for n intervals. The linear scan is O(n), making the overall time complexity O(n log n).**Space Complexity**: The space complexity is O(1) or O(n), depending on whether the sorting algorithm used is in-place. In the Python implementation provided, the sort is in-place, and the additional space used is for the`merged`

list.

### Algorithm Usage #

This algorithm is widely used in problems involving intervals, such as calendar scheduling, meeting rooms, and interval partitioning, due to its effectiveness in handling overlapping intervals with a sorted order.