本文主要是介绍435.无重叠区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
// 定义一个名为Solution的类
class Solution {// 定义公共方法eraseOverlapIntervals,输入为二维整数数组intervals,返回值类型为整数public int eraseOverlapIntervals(int[][] intervals) {// 首先,按照区间的起始位置对区间进行升序排序Arrays.sort(intervals, (a, b) -> {return Integer.compare(a[0], b[0]);});// 初始化计数器remove,用于记录需要移除的重叠区间数量int remove = 0;// 初始化变量pre,存储前一个区间的结束位置int pre = intervals[0][1];// 遍历整个区间数组,从第二个区间开始(下标i=1)for (int i = 1; i < intervals.length; i++) {// 检查当前区间(intervals[i])是否与前一个区间重叠if (pre > intervals[i][0]) {// 如果重叠,则增加需要移除的区间数量remove++;// 更新pre为前一个区间和当前区间结束位置的较小值,以便判断后续区间是否重叠pre = Math.min(pre, intervals[i][1]);} // 若当前区间与前一区间不重叠,则更新pre为当前区间的结束位置else {pre = intervals[i][1];}}// 返回需要移除的重叠区间数量return remove;}
}
这段代码实现了一个正确的解决方案,它可以找到并计算出在给定区间数组中为了消除所有重叠需要移除的区间数量。首先对区间按起始位置进行排序,然后遍历排序后的区间,如果当前区间与前一区间重叠,则增加移除计数器并更新pre为两区间结束位置的较小值。若不重叠则更新pre为当前区间的结束位置。最后返回移除的区间数量。
这篇关于435.无重叠区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!