codeforces 31 C. Schedule

http://codeforces.com/problemset/problem/31/C
题意:给出n个借用教室的时间安排,可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。
思路:首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。

如果没有任何冲突,那么答案为n,直接输出一遍就好。

以l为第一关键字,r为第二关键字升序sort下。

如果有一个冲突,那么要看是否有包含关系,如果有,需要去掉大的这个,方案数为1.如果只是相交,那么可以去掉任意一个。方案数为2.

如果有两个冲突,我要看这两个冲突涉及到几个时间安排,如果涉及到4个或者时间安排,那么不可能全部解决,die掉。

如果这两个冲突涉及到三个时间安排,也就是说中间的和两段的相交,那么可以取消中间的这个时间安排来解决冲突。方案数为1.

需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz