# 1. Introduction

The "Merge Intervals" problem is a common challenge in computational geometry and array manipulation. It involves merging overlapping intervals in a list, a task frequently encountered in areas like calendar event scheduling. This problem tests one’s ability to analyze and merge ranges efficiently.

## Problem

Given an array of *intervals* where each interval is defined as *[starti, endi]*, the task is to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

# 2. Solution Steps

1. Sort the *intervals* array based on the start times.

2. Initialize a list *merged* to hold the merged intervals.

3. Iterate through the sorted intervals.

4. For each interval, if the *merged* list is empty or if the current interval does not overlap with the last interval in *merged*, simply append it.

5. If there is an overlap, merge the current interval with the last interval in *merged* by updating the end time.

6. Return the *merged* list.

# 3. Code Program

```
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
# Example Usage
print(merge([[1,3],[2,6],[8,10],[15,18]])) # Output: [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]])) # Output: [[1,5]]
```

### Output:

[[1,6],[8,10],[15,18]] [[1,5]]

### Explanation:

**1. Sorting**: Intervals are sorted based on their start times to align overlaps.

**2. Merging Logic**: Determines whether to merge intervals or add them as is.

**3. Overlap Check**: Checks if the current interval overlaps with the last one in *merged*.

**4. Update Merged Intervals**: If there's an overlap, updates the end time of the last interval in *merged*.

**5. Efficient Solution**: Achieves O(n log n) time complexity due to sorting.

**6. Applicability**: Demonstrates an approach to handling and merging ranges, useful in event scheduling and range queries.

## Comments

## Post a Comment