java_non_overlapping_intervals

Given an array of intervals intervals  where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Examples

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.

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.

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 <= 105
• intervals[i].length == 2
• 5 * 104 <= starti < endi <= 5 * 104

解析

給定一個 2D 陣列 intervals

每個 intervals[i] = [ $start_i, end_i$] 代表一段 $start_i$ < value ≤$end_i$ 的區間

當區間發生重疊時，透過移除掉一個區間來避免重疊

要求寫一個演算法找出最少移出多少區間可以讓原本的 intervals 變成都沒有重疊的區間

首先，先觀察什麼狀況會造成重疊

假設 intervals[i] = [$start_i, end_i$], intervals[j] = [$start_j, end_j$]

if $start_i$ ≤ $start_j$

則兩個區間要重疊代表 $start_j$ < $end_i$

當兩個區間重疊，假設希望移除最少的區間

代表就是要留下最小的 end 當作 overlapEnd 來做比較

透過以上概念

我們需要先針對 intervals 根據 start 來做 sorting時間複雜度是 O(nlogn)

然後 初使化 count = 0, overlapEnd = intervals[0][1]

從 pos = 2 開始比較 intervals[pos][0] 是否小於 overlapEnd

如果是, 代表有重疊 需要更新 count = count + 1, 更新 overlapEnd = min(intervals[pos][1], overlapEnd)

如果否, 代表沒有重疊 繼續更新 overlapEnd = intervals[pos][1]

當比完所有的區間

count 就是所求

時間複雜度是 O(nlogn) 因為後面的執行其實只要要 loop n

空間複雜是 O(1)

程式碼

class Solution {
  public int eraseOverlapIntervals(int[][] intervals) {
    int count = 0;
    Arrays.sort(intervals, (a ,b) -> (a[0]- b[0]));
    int overlapEnd = intervals[0][1];
    int nIntervals = intervals.length;
    for (int pos = 1; pos < nIntervals; pos++) {
      if (overlapEnd > intervals[pos][0]) {
        overlapEnd = Math.min(overlapEnd, intervals[pos][1]);
        count++;
      } else {
        overlapEnd = intervals[pos][1];
      }
    }
    return count;
  }
}

困難點

1. 需要掌握重疊的特性
2. 需要理解最小移除數需要找出最小的 overlapEnd

Solve Point

• 對 intervals 根據 start 來做 sorting
• 初使化 count = 0, overlapEnd = intervals[0][1]
• 從 pos = 2 開始比較 intervals[pos][0] 是否小於 overlapEnd
• 如果是, 代表有重疊 需要更新 count = count + 1, 更新 overlapEnd = min(intervals[pos][1], overlapEnd)
• 如果否, 代表沒有重疊 繼續更新 overlapEnd = intervals[pos][1]
• 當比完所有的區間 count 就是所求