无重叠区间

/*
 * 思路：
 * 1. 首先将区间按照结束时间进行排序。
 * 2. 使用贪心算法，从第一个区间开始选择，每次选择结束时间最早且不与前一个选择的区间重叠的区间。
 * 3. 计算需要移除的区间数量。
 */
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
 
public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按照区间的结束时间进行排序
        List<int[]> sortedIntervals = Arrays.stream(intervals)
                .sorted((a, b) -> Integer.compare(a[1], b[1]))
                .collect(Collectors.toList());
        int count = 0;
        int end = sortedIntervals.get(0)[1];
        for (int i = 1; i < sortedIntervals.size(); i++) {
            if (sortedIntervals.get(i)[0] < end) {
                // 当前区间与前一个区间重叠，计数加一
                count++;
            } else {
                // 更新结束时间
                end = sortedIntervals.get(i)[1];
            }
        }
        return count;
    }
}