LeetCode 435. Non-overlapping Intervals

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });
        const int n = intervals.size();
        int right = intervals[0][1];
        int remains = 1;
        for (int i = 1; i < n; ++i)
            if (intervals[i][0] >= right) {
                ++remains;
                right = intervals[i][1];
            }
        return n - remains;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int n = intervals.length;
        int right = intervals[0][1];
        int remains = 1;
        for (int i = 1; i < n; ++i)
            if (intervals[i][0] >= right) {
                ++remains;
                right = intervals[i][1];
            }
        return n - remains;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals: return 0
        intervals.sort(key = lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        remains = 1
        for i in range(1, n):
            if intervals[i][0] >= right:
                remains += 1
                right = intervals[i][1]
        return n - remains