To make the photograph look nice, he wants the cows to line up in a single row from shortest to tallest. Unfortunately, right after he has the cows line up this way, Bessie the cow, always the troublemaker, steps out of line and re-inserts herself at some other location in the lineup!
Farmer John would like to swap pairs of cows so the entire herd is again lined up properly. Please help him determine the minimum number of swaps he needs to make between pairs of cows in order to achieve this goal.
FJ为他的奶牛们建造了一个游泳池,FJ认为这将有助于他们放松身心以及生产更多牛奶。
为了确保奶牛们的安全,FJ雇佣了N头牛,作为泳池的救生员,每一个救生员在一天内都会有一定的事情,并且这些事情都会覆盖一天内的一段时间。为了简单起见,泳池从时间t=0时开门,直到时间t=1000000000关门,所以每个事情都可以用两个整数来描述,给出奶牛救生员开始以及结束事情的时间。例如,一个救生员在时间t=4时开始事情并且在时间t=7时结束事情,那么这件事情就覆盖了3个单位时间。(注意:结束时间是“点”的时间)
不幸的是,FJ多雇佣了一名的救生员,但他没有足够的资金来雇佣这些救生员。因此他必须解雇一名救生员,求可以覆盖剩余救生员的轮班时间的最大总量是多少?如果当时至少有一名救生员的事情已经开始,则这个时段被覆盖。
输入格式
输入的第一行包括一个整数N(1≤N≤100000)。接下来N行中,每行告诉了我们一个救生员在0~10000000000范围内的开始以及结束时间。所有的结束时间都是不同的。不同的救生员的事情覆盖的时间可能会重叠。
输出格式
如果FJ解雇一名救生员仍能覆盖的最大时间。
感谢@Shan_Xian 提供的翻译
6
2
4
7
7
9
3
3
In this example, Bessie is clearly the cow of height 3. FJ return the cows to sorted order using three swaps as described below:
2 4 7 7 9 3 - Original Lineup 2 4 7 7 3 9 - Swap the last two cows 2 4 3 7 7 9 - Swap the first 7 and 3 2 3 4 7 7 9 - Swap 4 and 3