当前位置:网站首页>[interval problem] 435 Non overlapping interval
[interval problem] 435 Non overlapping interval
2022-07-05 05:16:00 【lee2813】
One 、 subject
Given a set of intervals , Find the minimum number of intervals to remove , Keep the remaining intervals from overlapping .
Be careful :
It can be said that the end of an interval is always greater than its starting point .
Section [1,2] and [2,3] The boundaries of each other “ Contact ”, But there is no overlap .
Example 1:
Input : [ [1,2], [2,3], [3,4], [1,3] ]
Output : 1
explain : remove [1,3] after , There's no overlap in the rest .
Example 2:
Input : [ [1,2], [1,2], [1,2] ]
Output : 2
explain : You need to remove two [1,2] So that the rest of the intervals don't overlap .
Example 3:
Input : [ [1,2], [2,3] ]
Output : 0
explain : You don't need to remove any intervals , Because they are already non overlapping .
Two 、 Answer key
This problem involves removing the minimum number of intervals , Analysis leads to , To make the last number of intervals reserved more , As long as the value at the end of each interval is small enough . therefore , The greedy strategy is to preferentially keep the disjoint intervals with small endings .
- First , Sort each interval according to the element at the end of the interval ( Ascending )
- then , Compare the end element value of the interval with the start value to judge whether the interval intersects , Until the end of the comparison interval
The determination of the intersection of intervals in this question :
Start from the end of the first interval , Compare with the starting element of the next interval , If the starting element of the next interval is less than prev1, Then it means that the next interval overlaps with it , discarded . In this way, it is compared with the starting element of the lower interval in turn , Until the starting element of the next interval is greater than prev1, Description no overlap , to update prev2 Is the end element of the interval , cycle .
3、 ... and 、 Code
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.empty()) return 0;
int n = intervals.size();
sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){
return a[1]<b[1];
});
int total = 0,prev = intervals[0][1];
for(int i = 1;i<n;i++){
if(intervals[i][0]<prev) total++;
else prev = intervals[i][1];
}
return total;
}
};
边栏推荐
- win下一键生成当日的时间戳文件
- Personal required code
- 2022/7/2 question summary
- Research on the value of background repeat of background tiling
- UE4/UE5 虚幻引擎,材质篇,纹理,Compression and Memory压缩和内存
- A three-dimensional button
- Chinese notes of unit particle system particle effect
- Insert sort
- Embedded database development programming (V) -- DQL
- PMP考生,请查收7月PMP考试注意事项
猜你喜欢
Unity ugui source code graphic
嵌入式数据库开发编程(零)
Redis has four methods for checking big keys, which are necessary for optimization
[trans]: spécification osgi
Reverse one-way linked list of interview questions
National teacher qualification examination in the first half of 2022
Embedded database development programming (zero)
UE 虚幻引擎,项目结构
Embedded database development programming (V) -- DQL
小程序直播+電商,想做新零售電商就用它吧!
随机推荐
3dsmax2018 common operations and some shortcut keys of editable polygons
3dsmax common commands
【论文笔记】Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research
Solon Logging 插件的添加器级别控制和日志器的级别控制
Download xftp7 and xshell7 (official website)
[LeetCode] 整数反转【7】
Lua determines whether the current time is the time of the day
2020-10-27
PR first time
LeetCode之单词搜索(回溯法求解)
PMP考试敏捷占比有多少?解疑
小程序直播+電商,想做新零售電商就用它吧!
2022年上半年国家教师资格证考试
Unity sends messages and blocks indecent words
LeetCode之單詞搜索(回溯法求解)
Generate filled text and pictures
使用Room数据库报警告: Schema export directory is not provided to the annotation processor so we cannot expor
2022/7/1 learning summary
GBase数据库助力湾区数字金融发展
UE fantasy engine, project structure