# Intervals — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/intervals

> Merging overlaps and scheduling non-overlapping intervals — both start with sorting.

## Sort first, always

Almost every interval problem starts by **sorting intervals by start time** (or end time for scheduling). Once sorted, overlaps and gaps become adjacent comparisons instead of an all-pairs search.

## Merge overlapping intervals

After sorting by start, walk through and merge whenever the current interval's start is `<=` the last merged interval's end.

```python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    return merged
```

Output:

```
merge([[1,3],[2,6],[8,10],[15,18]])
# [[1,6],[8,10],[15,18]]
```

## Interval scheduling (max non-overlapping)

To fit the **most non-overlapping intervals**, sort by **end time** and greedily keep an interval whenever it starts after the last kept interval's end.

```python
def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count
```

Output:

```
max_non_overlapping([[1,2],[2,3],[3,4],[1,3]])  # 3
```

## Common variants

Insert a new interval into a sorted list, find minimum meeting rooms needed (use a heap of end times), and check if a person can attend all meetings — all built on the same sort-then-scan idea.