昨天是輸入新區段，今天要做的是移除區段。
題目給定一組區段的陣列，陣列中包含的每個區段，有可能跟其他區段有重疊。
我們需要設計演算法移除區段的最小數量，使剩餘區段互不重疊。

題目

https://leetcode.com/problems/non-overlapping-intervals/

Given an array of 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.

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

我的答案

貪婪演算法: 優先保留結尾小且不相交的區間。.

先把區段按照結尾的大小進行排序，然後對每個區段與前ㄧ個區段比對，如果沒有重疊，則將該區段保留．但如果跟前一個區段有重疊，則捨棄目前的區段。

譬如：
給區段陣列 A = [[1,2],[2,3],[3,4],[1,3]]
按照結尾大小排序後 = [[1,2],[2,3],[1,3],[3,4]]
[1,2]為初始區段。
[1,2]跟[2,3]沒有重疊，所以[2,3]可以保留。
[2,3]跟[1,3]重疊，所以捨棄目前[1,3]區段。
[2,3]跟[3,4]沒有重疊，所以[3,4]也保留。

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        pre, removeCount = 0, 0
        for i in range(1, len(intervals)) :
            if intervals[pre][1] > intervals[i][0]:
                removeCount += 1
            else:
                pre = i
        return removeCount

import (
    "sort"
)

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    preIndex := 0
    removeCount := 0
    for i := 1; i < len(intervals); i++ {
        if intervals[preIndex][1] > intervals[i][0] {
            removeCount++
        } else {
            preIndex = i
        }
    }
    return removeCount
}