2022.01.03 - SX09-18.无重叠区间

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

• 可以将统计最小数量重叠区间问题转换成统计最大数量无重叠区间问题。
• 先将所有区间按照右端点从小到大进行排序，这样可以保证从左往右遍历时，若区间的左端点大于等于前一个区间的右端点，则这两个区间必然不重叠。

import java.util.Arrays;
import java.util.Comparator;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int n = intervals.length;
        int count = 1;
        int right = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] >= right) {
                count++;
                right = intervals[i][1];
            }
        }
        return n - count;
    }
}