435. Non-overlapping Intervals - Medium

前往題目

想法

• 用掃描線，但實作卡住了

思路

1. 用每個array的第一項排序
2. 以第一項為基準開始疊代確認是否相交
3. 如果不相交就更新區間的尾端
4. 如果相交，多一個需要移除，並且取比較小的尾端，這樣可以減低之後再相交的機率

Code

// T: O(nlogn)
// S: O(1)
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 1)
            return 0;

        // Sort by the first element
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int res = 0;
        int prevEnd = intervals[0][1];

        // Start from the second item
        for (int i = 1; i < intervals.length; ++i) {
            // Not overlapping
            if (prevEnd <= intervals[i][0]) {
                prevEnd = intervals[i][1];
            } else { // Overlapping
                ++res;
                // Pick the smaller end to minimize the overlapping possibility
                prevEnd = Math.min(prevEnd, intervals[i][1]);
            }
        }

        return res;
    }
}