锐客网

  1. 首页 > it技术 > >

区间包含问题

【区间包含问题】对于一些区间和一条线段，要用最少的区间来包含这条线段（s，t）（s是起点，t是终点），求最小区间数；
首先要对区间做一下预处理，把终点大于t的区间全部改为t；因为大于t的区间是没有用的，（也可以不改，条件改成判断大于等于就可以）
然后要找一个最接近s并小于s的起点A[i].s，怎么找呢，就是在预处理的时候，排完序后，（排序的方法：排起点，如果在for中加一个判断，如果A[cnt].s<= s; cnt++；除了循环后要判断是否存在这样一个点，就是如果cnt == 0，证明判断一直没成功，所以不存在这样一个点，否则的话就cnt–；因为如果存在这样一个点，在循环中cnt++了，比应该的位置加了一，所以要–；还要判断是否存在A[n-1].t是否大于等于t，如果不大于，证明不可行，即不会被包含，就错误；还要判断给定的区间会不会出现分离的情况，比如（(3,4), (5,6)），这样是不满足的，怎么判断呢，遍历一下，然后判断A[i].s是否大于A[i-1].t,为了正确，输入从1开始，A[0].t设为1000；如果是，退出，st = 1，证明不行；在三个条件都满足后，进行下一步，int cur = cnt; 判断s是否等于t；如果不等于，s = A[cur++].t; 直到等于t；跳出循环，输出cur - cnt，即最小区间的个数；

#include #include using namespace std; const int maxn = 1e5+10; struct Interval { int s; int t; }A[maxn]; int cmp2(Interval x, Interval y) { if(x.s == y.s) return x.t < y.t; return x.s < y.s; }int main() { int n, s, t; while(scanf("%d",&n) == 1) { int cnt = 1; for(int i = 1; i <= n; i++) scanf("%d %d",&A[i].s,&A[i].t); scanf("%d%d",&s,&t); sort(A,A+n,cmp2); for(int i = 1; i <= n; i++) { if(A[cnt].s <= s) cnt++; if(A[i].t > t) A[i].t = t; } A[0].t = 1000; if(cnt == 0 || A[n].t < t){ printf("-1\n"); continue; } else cnt--; int st = 0; for(int i = cnt+1; i<= n; i++) if(A[i].s > A[i-1].t){ st = 1; break; } if(st){ printf("-1\n"); continue; } int cur = cnt; while(s != t) s = A[cur++].t; printf("%d\n",cur-cnt); } return 0; }

    推荐阅读


    上一篇：ROS系统是编写机器人软件的灵活框架，方便在各种平台上创建复杂的机器人。

    下一篇：javascript设计模式（二） 代理模式 观察者模式