---
title: "算法面試套路｜合併區間（Merge Intervals）"
description: "Patterns for Coding Questions: Merge Intervals."
image: https://i.imgur.com/7jiNtkx.png
author: Hsins
tags: LeetCode, Coding Interview
robots:
breaks:
GA:
disqus:
---
# 算法面試套路｜合併區間（Merge Intervals）
<p style="text-align: center">
<img src="https://i.imgur.com/7jiNtkx.png" height=200/>
</p>
> 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。
## 重點整理
- 合併區間（Merge Intervals）
- 策略：給定兩個區間，彼此之間共有六種不同的交互模式
- 題型：
- 涉及間隔（intervals）的問題
- 找尋重疊部分、合併重疊間隔
## 題目匯總
- `0056` Merge Intervals
- `0057` Insert Interval
- `0252` Meeting Rooms
- `0253` Meeting Rooms II
- `0435` Non-overlapping Intervals
- `0729` My Calendar I
- `0759` Employee Free Time
- `0986` Interval List Intersections
- `1094` Car Pooling
- `1288` Remove Covered Intervals
## [例題] Merge Intervals
### 問題
給定一個區間陣列，合併所有重疊的區間，並返回這些區間所組成的陣列。比如 `[[1,4], [2,5], [7,9]]` 合併後會得到 `[[1,5], [7,9]]`：
<p style="text-align: center">
<img src="https://i.imgur.com/Rt7imGE.png" />
</p>
**Exapmles**
```
Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]], Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].
Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]], Since all the given intervals overlap, we merged them into one.
```
### 題解
考慮兩個區間 `a` 和 `b` 滿足 `a.start <= b.start`，一共會有四種交互情況：
<table>
<tr>
<th>狀況</th>
<th>圖示</th>
</tr>
<tr>
<td>
1. 彼此不重疊
2. 部分的 `b` 與 `a` 重疊
3. 所有的 `b` 在 `a` 裡面
4. 所有的 `a` 在 `b` 裡面，且起點相同
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/4pna3R1.png" />
</p>
</td>
</tr>
</table>
我們的目標是要合併重複區間，依據上述 (2), (3), (4) 的重疊情況，合併的方式如下：
<p style="text-align: center">
<img src="https://i.imgur.com/gbPKMwJ.png" />
</p>
```
c.start = a.start // 左側固定
c.end = max(a.end, b.end) // 右側取大
```
因此我們的演算法策略為：
1. 先將所有的區間進行排序，確保 `a.start <= b.start`
2. 如果發生「重疊」（即 `b.start <= a.end`）的狀況，需要合併為新的區間 `c`
3. 反覆上述動作，如果下一個區間與得到的區間 `c` 有重疊的狀況
### 代碼
#### C++
``` cpp
class MergeIntervals {
public:
static vector<Interval> mergeIntervals(vector<Interval> &intervals) {
if (intervals.size() < 2) {
return intervals;
}
sort(intervals.begin(), intervals.end(),
[](const Interval &x, const Interval &y) { return x.start < y.start; });
vector<Interval> mergedIntervals;
vector<Interval>::const_iterator intervalItr = intervals.begin();
Interval interval = *intervalItr++;
int start = interval.start;
int end = interval.end;
while (intervalItr != intervals.end()) {
interval = *intervalItr++;
if (interval.start <= end) {
end = max(interval.end, end);
} else {
mergedIntervals.push_back({ start, end });
start = interval.start;
end = interval.end;
}
}
mergedIntervals.push_back({ start, end });
return mergedIntervals;
}
}
```
#### Java
``` java
class MergeIntervals {
public static List<Interval> merge(List<Interval> intervals) {
if (intervals.size() < 2) {
return intervals;
}
// sort the intervals by start index
Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
List<Interval> mergedIntervals = new LinkedList<Interval>();
Iterator<Interval> intervalItr = intervals.iterator();
Interval interval = intervalItr.next();
int start = interval.start;
int end = interval.end;
while (intervalItr.hasNext()) {
interval = intervalItr.next();
if (interval.start <= end) { // overlapping intervals, adjust the end
end = Math.max(interval.end, end);
} else { // non-overlapping interval, add the previous interval and reset
mergedIntervals.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
// add the last interval
mergedIntervals.add(new Interval(start, end));
return mergedIntervals;
}
}
```
#### JavaScript
``` javascript
const mergeIntervals = (intervals) => {
if (intervals.length < 2) {
return intervals;
}
intervals.sort((a, b) => a.start - b.start);
const mergedIntervals = [];
let start = intervals[0].start;
let end = intervals[0].end;
for (let i = 1; i < intervals.length; ++i) {
const interval = intervals[i];
if (interval.start <= end) {
end = Math.max(interval.end, end);
} else {
mergedIntervals.push(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
mergedIntervals.push(new Interval(start, end));
return mergedIntervals;
}
```
#### Python
``` python
def merge_intervals(intervals):
if len(intervals) < 2:
return intervals
intervals.sort(key=lambda x: x.start)
mergedIntervals = []
start = intervals[0].start
end = intervals[0].end
for i in range(1, len(intervals)):
interval = intervals[i]
if interval.start <= end:
end = max(interval.end, end)
else:
mergedIntervals.append(Interval(start, end))
start = interval.start
end = interval.end
mergedIntervals.append(Interval(start, end))
return mergedIntervals
```
### 分析
- 時間複雜度：$\mathcal{O}(n\log{n})$，其中遍歷需 $\mathcal{O}(n)$ 而排序需 $\mathcal{O}(n\log{n})$，又 $\mathcal{O}(n\log{n}) > \mathcal{O}(n)$
- 空間複雜度：$\mathcal{O}(n)$，需要 $\mathcal{O}(n)$ 進行排序且需要 $\mathcal{O}(n)$ 用來儲存返回的區間陣列
## [例題] Insert Interval
### 問題
給定一個由不重疊區間所組成的陣列，並且該陣列已經根據起始位置進行排序，將一個額外給定的區間插入正確的位置，並合併重疊區間使返回的區間陣列中為彼此獨立的區間。
**Examples**
```
Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]], After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].
Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]], After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].
Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]], After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].
```
### 題解
倘若給定陣列並未排序，我們可以簡單地將新的區間添加至陣列中，並呼叫 [Merge Intervals](#例題-Merge-Intervals) 中的 `merge()` 函數來處理。但既然題目已經說給定的陣列 **有序**，我們需要想看看是否能夠有比 $\mathcal{O}(n\log{n})$ 更好的解決方法。
當我們要在一個已經排序的區間陣列中插入一個新的區間時，<mark>首先需要找到可以放置新區間的正確位置</mark>；換句話說，我們需要跳過在新區間開始前之前結束的所有區間，亦即遍歷區間陣列，並使用以下條件跳過這些不滿足條件的區間：
```
intervals[i].end < newInterval.start
```
找到正確的位置後，可以遵循類似於 [Merge Intervals](#例題-Merge-Intervals) 的做法來插入或合併新的區間。在不失一般性的情況下將新區間稱為 `a`，而滿足上述條件的第一個區間稱為 `b`，則共有以下五種可能性：
<table>
<tr>
<th>狀況</th>
<th>圖示</th>
</tr>
<tr>
<td>
1. 彼此不重疊，直接插入 `a`
2. 部分的 `b` 與 `a` 重疊，合併為 `c(a.start, b.end)`
3. 所有的 `b` 在 `a` 裡面，合併為 `c(a.start, a.end)`
4. 部分的 `a` 與 `b` 重疊，合併為 `c(b.start, a.end)`
5. 所有的 `a` 在 `b` 裡面，合併為 `c(b.start, b.end)`
</td>
<td>
<p style="text-align: center">
<img src="https://i.imgur.com/Y1VXsyq.png" />
</p>
</td>
</tr>
</table>
要處理上述 (2), (3), (4) 和 (5) 的重疊狀況，只需要執行以下操作：
```
c.start = min(a.start, b.start) // 左側取小
c.end = max(a.end, b.end) // 右側取大
```
因此我們的演算法策略為：
1. 遍歷陣列跳過滿足 `intervals[i].end < newInterval.start` 的區間
2. 找到不滿足條件的區間，判斷左右邊界並合併得到新區間 `c`
3. 反覆上述動作，如果下一個區間與得到的區間 `c` 有重疊的狀況
### 代碼
#### C++
``` cpp
class InsertInterval {
public:
static vector<Interval> insert(const vector<Interval> &intervals, Interval newInterval) {
if (intervals.empty()) {
return vector<Interval> { newInterval };
}
vector<Interval> mergedIntervals;
int idx = 0;
while (idx < intervals.size() && intervals[idx].end < newInterval.start) {
mergedIntervals.push_back(intervals[idx]);
idx++;
}
while (idx < intervals.size() && intervals[idx].start <= newInterval.end) {
newInterval.start = min(intervals[idx].start, newInterval.start);
newInterval.end = max(intervals[idx].end, newInterval.end);
idx++;
}
mergedIntervals.push_back(newInterval);
while (idx < intervals.size()) {
mergedIntervals.push_back(intervals[idx]);
idx++;
}
return mergedIntervals;
}
}
```
#### Java
``` java
class InsertInterval {
public static List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (intervals == null || intervals.isEmpty()) {
return Arrays.asList(newInterval);
}
List<Interval> mergedIntervals = new ArrayList<>();
int i = 0;
// skip (and add to output) all intervals that come before the newInterval
while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
mergedIntervals.add(intervals.get(i++));
}
// merge all intervals that overlap with newInterval
while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
i++;
}
// insert the newInterval
mergedIntervals.add(newInterval);
// add all the remaining intervals to the output
while (i < intervals.size()) {
mergedIntervals.add(intervals.get(i++));
}
return mergedIntervals;
}
}
```
#### JavaScript
``` javascript
const insertInterval = (intervals, newInterval) {
let idx = 0;
let merged = [];
while (idx < intervals.length && intervals[idx].end < newInterval.start) {
merged.push(intervals[idx]);
idx += 1;
}
while (idx < intervals.length && intervals[idx].start <= newInterval.end) {
newInterval.start = Math.min(intervals[idx].start, newInterval.start);
newInterval.end = Math.max(intervals[idx].end, newInterval.end);
idx += 1;
}
merged.push(newInterval);
while (idx < intervals.length) {
merged.push(intervals[idx]);
i += 1;
}
return merged;
}
```
#### Python
``` python
def insert_interval(intervals, new_interval):
merged = []
i = 0
start = 0
end = 1
while i < len(intervals) and intervals[i][end] < new_interval[start]:
merged.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][start] <= new_interval[end]:
new_interval[start] = min(intervals[i][start], new_interval[start])
new_interval[end] = max(intervals[i][end], new_interval[end])
i += 1
merged.append(new_interval)
while i < len(intervals):
merged.append(intervals[i])
i += 1
return merged
```
### 分析
- 時間複雜度：$\mathcal{O}(n)$
- 空間複雜度：$\mathcal{O}(n)$
## [例題] Intervals Intersection
### 問題
給定兩個區間陣列，找出兩個陣列的交集部分，每一個陣列中的區間彼此獨立且已經依據起始位置進行排序。
**Examples**:
```
Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7].
Input: arr1=[[1, 3], [5, 7], [9, 12]], arr2=[[5, 10]]
Output: [5, 7], [9, 10].
```
### 題解
這個問題可以採用 **合併區間（Merge Intervals）** 模式求解，正如我們在 [Insert Interval](#例題-Insert-Interval) 中所討論的，在兩個間隔 `a` 和 `b` 之間有五種交互的狀況；仔細觀察不難發現，每<mark>當兩個區間重疊時，其中一個區間的開始位置會位於另外一個區間中</mark>，這個事實可以幫助我們確認兩個區間是否重疊。
<p style="text-align: center">
<img src="https://i.imgur.com/SGjdmS4.png" />
</p>
此時，兩個重疊區間交集的部分，可以透過以下方式判斷其區間：
```
start = max(a.start, b.start) // 左側取大
end = min(a.end, b.end) // 右側取小
```
因此我們只需要遍歷兩個陣列，同時查看是否有區間重疊，重疊的部分計算其交集並插入結果陣列中，直到結束。
### 代碼
#### C++
``` cpp
class Intersection {
public:
static vector<Interval> merge(const vector<Interval> &arr1, const vector<Interval> &arr2) {
vector<Interval> result;
int i = 0;
int j = 0;
while (i < arr1.size() && j < arr2.size()) {
if ((arr1[i].start >= arr2[j].start) && arr1[i].start <= arr2[j].end) ||
(arr2[j].start >= arr1[i].start) && arr2[j].start <= arr1[i].end)) {
result.push_back({max(arr1[i].start, arr2[j].start), min(arr1[i].end, arr2[j].end)});
}
if (arr1[i].end < arr2[j].end) {
i++;
} else {
j++;
}
}
return result;
}
};
```
#### Java
``` java
class IntervalsIntersection {
public static Interval[] merge(Interval[] arr1, Interval[] arr2) {
List<Interval> result = new ArrayList<Interval>();
int i = 0;
int j = 0;
while (i < arr1.length && j < arr2.length) {
if ((arr1[i].start >= arr2[j].start && arr1[i].start <= arr2[j].end)
|| (arr2[j].start >= arr1[i].start && arr2[j].start <= arr1.[i].end)) {
result.add(new Interval(Math.max(arr1[i].start, arr2[j].start), Max.min(arr1[i].end, arr2[j].end)));
}
}
if (arr1[i].end < arr2[j].end) {
i++;
} else {
j++;
}
return result.toArray(new Interval[result.size()]);
}
}
```
#### JavaScript
``` javascript
const IntersectionIntervals = (intervals_a, intervals_b) => {
let results = [];
let i = 0;
let j = 0;
while (i < intervals_a.length && j < intervals_b.length) {
if ((intervals_a[i].start >= intervals_b[j].start && intervals_a[i].start <= intervals_b[j].end) ||
(intervals_b[j].start >= intervals_a[i].start && intervals_b[j].start <= intervals_a[i].end)) {
const left = Math.max(intervals_a[i].start, intervals_b[j].start);
const right = Math.min(intervals_a[i].end, intervals_b[j].end);
result.push(newInterval(left, right));
}
if (intervals_a[i].end < intervals_b[j].end) {
i += 1;
} else {
j += 1;
}
}
return result;
}
```
#### Python
``` python
def intersection(intervals_a, intervals_b):
result = []
i, j, start, end = 0, 0, 0, 1
while i < len(intervals_a) and j < len(intervals_b):
a_overlaps_b = intervals_a[i][start] >= intervals_b[j][start] and intervals_a[i][start] <= intervals_b[j][end]
b_overlaps_a = intervals_b[j][start] >= intervals_a[i][start] and intervals_b[j][start] <= intervals_a[i][end]
if (a_overlaps_b or b_overlaps_a):
result.append([max(intervals_a[i][start], intervals_b[j][start]), min(intervals_a[i][end], intervals_b[j][end])])
if intervals_a[i][end] < intervals_b[j][end]:
i += 1
else:
j += 1
return result
```
### 分析
- 時間複雜度：$\mathcal{O}(n+m)$
- 空間複雜度：$\mathcal{O}(n+m)$，若不計返回陣列所需的空間則為 $\mathcal{O}(1)$
## [例題] Conflicting Appointments
給定一組陣列，其中有 $N$ 個約會行程（以區間表示時間範圍），撰寫一支程式判斷一個人是否可以出席所有的約會行程。
### 問題
**Examples**
```
Input: [[1,4], [2,5], [7,9]]
Output: false. Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.
Input: [[6,7], [2,4], [8,12]]
Output: true. None of the appointments overlap, therefore a person can attend all of them.
Input: [[4,5], [2,3], [3,6]]
Output: false. Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.
```
### 題解
這個問題可以採用 **合併區間（Merge Intervals）** 模式求解，我們需要做的是先將約會行程依據起始時間進行排序，再逐個確認這些區間是否存在重疊的狀況。
> 1. 注意判斷的邊界需不需要包含
> 2. 存在重疊的條件
### 代碼
#### C++
``` cpp
class ConflictingAppointments {
public:
static bool canAttendAllAppointments(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), [](const Interval& x, const Interval& y) { return x.start < y.start; });
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
}
```
#### Java
``` java
class ConflictingAppointments {
public static boolean canAttendAllAppointments(Interval[] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
}
```
#### JavaScript
``` javascript
const canAttendAllAppointments = (intervals) => {
intervals.sort((a, b) => a.start - b.start);
for (let i = 1; i < intervals.length; i++) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
```
#### Python
``` python
def can_attend_all_appointments(intervals):
intervals.sort(key=lambda x: x[0])
start, end = 0, 1
for i in range(1, len(intervals)):
if intervals[i][start] < intervals[i-1][end]:
return False
return True
```
### 分析
- 時間複雜度：$\mathcal{O}(n\log{n})$
- 空間複雜度：$\mathcal{O}(n)$ 排序所需空間
## 參考資料
- [Merge Overlapping Intervals | GeeksforGeeks](https://www.geeksforgeeks.org/merging-intervals/)
- [Coding Patterns: Merge Intervals | emre.me](https://emre.me/coding-patterns/merge-intervals/#similar-leetcode-problems)
<!-- Widget: License -->
{%hackmd @Hsins/widget-license %}
Sign in with Wallet
Connect another wallet