# Intervals — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Overlaps मिलाना और non-overlapping intervals को schedule करना — दोनों sorting से शुरू होते हैं।

## पहले हमेशा sort करें

लगभग हर interval समस्या **intervals को start time से sort करने** से शुरू होती है (scheduling के लिए end time से)। Sort होने के बाद, overlaps और gaps all-pairs खोज के बजाय पड़ोसी तुलना बन जाते हैं।

## Overlapping intervals मिलाएँ

Start से sort करने के बाद, आगे बढ़ें और जब भी मौजूदा interval का start, आखिरी merged interval के 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 (अधिकतम non-overlapping)

**सबसे अधिक non-overlapping intervals** फिट करने के लिए, **end time** से sort करें और जब भी कोई interval पिछले रखे गए interval के end के बाद शुरू हो, उसे greedily रखें।

```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
```

## आम variants

एक sorted list में नया interval डालना, न्यूनतम meeting rooms चाहिए (end times का heap इस्तेमाल करें), और क्या कोई व्यक्ति सभी meetings में जा सकता है — सब उसी sort-फिर-scan विचार पर बने हैं।