stdKonjac's Blog

An AC a day keeps the WA away ~

【CodeVS 1214 线段覆盖】

题目描述 Description

    给定x轴上的N(0<N<100)条线段,每个线段由它的二个端点a_I和b_I确定,I=1,2,……N.这些坐标都是区间(-999,999)的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序,从给出的线段中去掉尽量少的线段,使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部(即除去端点的部分)。

输入描述 Input Description

    输入第一行是一个整数N。接下来有N行,每行有二个空格隔开的整数,表示一条线段的二个端点的坐标。

样例输入 Sample Input

3

6  3

1  3

2  5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

0<N<100

直接贪就好了,对左端点排个序,对于每一条线段,如果它的起点比当前终点远,肯定选它,如果它的终点比当前终点近,答案不变,替换当前终点(因为起点已经排序了,这样一定最优),如果有交叉,肯定不选它,因为它的终点还更远,并且选了它答案不变。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.