[ LeetCode ] [ Kotlin ] - 435. Non-overlapping Intervals 難度 ★★ @ 西瓜是肥貓

先看看題目：

435. Non-overlapping Intervals

Medium

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

附上通關證明：

截圖 2020-08-18 下午6.18.21

我的想法：題目是說計算有多少重複的區間，這題要注意的點是數列沒有被排序，所以先做排序就好做了，抓住最小的頭後，只要比數列的延伸就好，同樣頭的數列則先以短的尾部為主，因為如果一開始就以較大的尾端的話，有些延伸數列會直接被吃掉，所以再做一次尾端排序也是一種辦法，只是速度可能比較慢一點。

class Solution {
    fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
        if(intervals.size <= 1)
            return 0
        intervals.sortWith(compareBy({it.first()}, {it.first()}))
        var end =  intervals[0][1]
        var result = 0
        for(i in 1..intervals.size-1){
            val i_start = intervals[i].first()
            if(i_start >= end){
                end = intervals[i].last()
                continue
            }
            end = minOf(intervals[i].last(), end)
            result++
        }
        return result
    }
}