排序應用題: 不重複的區間 Non-overlapping Intervals_Leetcode #435_精選75題

Geert Pieters on Unsplash

題目敘述

題目會給定一個輸入陣列intervals，陣列元素都是一組pair，
intervals[i] = [start_i, end_i]，分別代表區間的起點，和區間的終點。

請問我們最少要刪除幾個區間，才能讓剩下的區間彼此都不重疊？

題目的原文敘述

測試範例

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
移除[1,3]可以讓剩下的區間都不重疊。​

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
移除多出來的兩個[1,2]可以讓剩下的區間都不重疊。

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
不需要移除，原本的區間已經都不重疊。

約束條件

Constraints:

• 1 <= intervals.length <= 10^5

輸入陣列長度介於1~十萬之間。

• intervals[i].length == 2

每個陣列元素都是一組Pair

• -5 * 10^4 <= starti < endi <= 5 * 10^4

起點、終點介於 負五萬~正五萬之間。

演算法 Greedy + 排序

想要讓所有區間都不重疊，可以想到先讓所有區間都依終點的大小作排序。

接下來，從左到右檢查每個區間，假如當下這個區間的起點比前面區間的終點還小，代表有重疊，必須刪除，依此類推，掃描並且檢查所有區間。

示意圖

image.png