刚刚开始入门算法oj,从贪心开始上手了。
给定一个区间的集合 intervals ,其中 intervals[i] = starti, endi,返回需要移除区间的最小数量,使剩余区间互不重叠 。
对二维vector数组设置一个pair对,首位元素存放区间左值末尾元素存放区间右值。从小到大排序后连接起来并计数总共能连接多少对,总区间数与连接对数count的差值就是要删减的最小数量。
然而WA了,不过用自己的测试用例跑出来的没发现问题;之前做过一个要求count的类似的练习也成功了。
可能会犯比较低级的错误,欢迎大家批评指正!
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
int num=intervals.size();
pair<int,int> work[num];
for(int i=0;i<num;i++)
{
work[i].first=intervals[i][0];
work[i].second=intervals[i][1];
}
sort(work,work+num);
int count=0;
int keep=0;
for(int i=0;i<num;i++)
{
if(keep<work[i].first)
{
count++;//count表示能够连接起来的区间数
keep=work[i].second;//连接后区间的起点
}
}
return (num-count);//区间总数减连接起来的区间数就是应该减去的数量
}
你好,我是有问必答小助手,非常抱歉,本次您提出的有问必答问题,技术专家团超时未为您做出解答
本次提问扣除的有问必答次数,将会以问答VIP体验卡(1次有问必答机会、商城购买实体图书享受95折优惠)的形式为您补发到账户。
因为有问必答VIP体验卡有效期仅有1天,您在需要使用的时候【私信】联系我,我会为您补发。