题意:有n个飞机,它们有早和晚降落时间,现在要使每个飞机都能下降,但是任意两个飞机不能同时降落,让你给飞机安排下落时间.另外使到任意两个飞机的降落的最短时间间隔最大.只是需要输出这个时间
最小值最大,这类问题就是二分答案了.我们枚举一个时间T,作为所有飞机降落的最短间隔,意思就是任意两个飞机的降落时间差都是大于等于这个T,如果能满足这个条件,那么这个T就是一个答案,既然这个答案满足,我们就可以试着去找一个更大的答案(因为我们是要最大值),所以就想上二分,如果这个T不满足,那么只好缩小这个T,向下二分.
至于怎么判定这个T是否合法,就要用2-sat了.我们先假定一个T成立,那么我们枚举任意两个飞机ij,他们的早晚降落时间分别为aibiajbj