435. Non-overlapping Intervals

    xiaoxiao2021-03-25  117

    一、题目简述

    给定一些区间,找到需要移除的最小区间数,以使剩余的区间之间没有重叠。 注意:

    区间的终点总是大于起点如同 [1,2][2,3] 这样的区间,虽然边界相连,但不重叠。

    示例1: 输入: [[1,2],[2,3],[3,4],[1,3]] 输出:1 解释:移除区间 [1,3] 示例2: 输入: [[1,2],[1,2],[1,2]] 输出:2 解释:移除区间 [1,2] 两次 示例3: 输入: [[1,2],[2,3]] 输出:0 解释:区间不重叠无需移除

    二、编程思路

    本题目的编程思路与“参加最多会议数”的思路相同,给定一系列会议的起点与终点,能够参加最多的会议,就是不参加最少的会议,且剩余的会议之间互不重叠。 因此,首先对Interval根据结束时间进行排序,排序原则:

    结束时间早的在前结束时间相同,开始时间晚的在前

    之后使用贪心算法,每次选择与当前已选择的区间不重叠的区间。若重叠,则记录移除区间数的 eraseNum++ ,若不重叠,将当前区间纳入已选择。

    三、程序设计

    /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ bool cmp(Interval in1,Interval in2){ if(in1.end!=in2.end){ return in1.end<in2.end; } else{ return in1.start<in2.start; } } class Solution { public: int eraseOverlapIntervals(vector<Interval>& intervals) { if(intervals.size()==0) return 0; sort(intervals.begin(),intervals.end(),cmp); /*for(int i=0;i<intervals.size();i++){ cout<<intervals[i].start<<" "<<intervals[i].end<<endl; }*/ int eraseNum=0; int endTime=intervals[0].end; for(int i=1;i<intervals.size();i++){ if(intervals[i].start>=endTime){ endTime=intervals[i].end; } else{ eraseNum++; } } return eraseNum; } };

    四、编程心得

    学会对问题进行适当转化。

    转载请注明原文地址: https://ju.6miu.com/read-9736.html

    最新回复(0)