备战Noip2018模拟赛10 (B组） T3 Inte 时间相交问题

时间相交问题"/>

备战Noip2018模拟赛10 (B组） T3 Inte 时间相交问题

10月20日备战Noip2018模拟赛10

T3 Inte时间相交问题

题目描述

巨佬CYX写了一张时间表，她有一段时间学习FFT，有时候研究NTT，有时候学习线性代数，有的时候研究PTSD，有时候研究弦理论，有时候看看德雷克方程，有时候解解千禧难题，有时候做做双缝实验，有时随意AK一下IOI，有时研究渐进自由量子，有时候看看对冷暗物质模型。

给一天（无数个小时，可以是负数）上n（n <1000）个时间段。去掉尽可能少的时间段，使剩下的时间段都不相交，这样笔的时间计划就不会冲突了。

给定ñ个时间段，编程计算去掉的最少时间段数。

输入格式

第一行是正整数N，表示闭时间段。接下来的ň行中，

    每行有2个整数，分别表示时间段的2个端点。

输出格式

将计算出的去掉的最少时间段数输出到文件inte.out

输入样例

3
10 20
10 15
20 15

输出样例

2

思路

贪心

先将几个区间按照右端点从小到大快排，用QL记录整个范围的起始位置初始为1
先选取右端点最靠前的，并将QL更新为这个区间的右端点。
在QL后面找完整的区间，并且选择右端点最靠前的
循环结束条件就是找不到完整区间了

代码

#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 1005;struct Node{int l;int r;
}a[N];int n, cnt, temp;bool cmp (const Node & a, const Node & b)
{if (a.r == b.r) return a.l < b.l;return a.r < b.r;
}int main ()
{//freopen ("inte.in", "r", stdin);//freopen ("inte.out", "w", stdout);scanf ("%d", & n);for (int i = 1; i <= n ; i ++){scanf ("%d %d", & a[i].l, & a[i].r);if (a[i].l > a[i].r) swap (a[i].l, a[i].r);}sort (a + 1, a + 1 + n, cmp);temp = a[1].r;for (int i = 2; i <= n; i ++){if (a[i].l > temp) temp = a[i].r;else cnt ++;}cout << cnt;//fclose (stdin);//fclose (stdout);return 0;
}