问题 4210 --2、最佳时间(time.pas/c/cpp)

4210: 2、最佳时间(time.pas/c/cpp)

题目描述

  泽泽不但喜欢看拳击比赛,而且也喜欢下围棋和编程,所以他决定参加围棋和编程兴趣班。
围棋兴趣班共有n个时间段选择,第i 个时间段排在(Li ~ Ri)。编程兴趣班也有m个时间段选择,第i 个时间段排在(Ai ~ Bi)。他必须要选择一个围棋班和一个编程班的时间段,但他希望选的这两个班中间的休息时间越长越好。
例如,他选了这两个时间段(L1 ~ R1)和(A1 ~ B1),假设(L1 ~ R1)这节课在前面,(A1 ~ B1)这节课在后面,那么,泽泽在中间休息的时间是A1-R1。特别说明,当两节课上课时间有冲突,泽泽在中间休息时间为 0。
泽泽想算一算他所选的两节兴趣课之间,能休息的时间最长是多少?请你帮助泽泽找一找,算一算。

输入

第一行输入一个整数n,表示围棋兴趣班可选择的时间段。
下列n行,每行都输入两个整数Li和Ri ,分别表示泽泽参加第i个围棋班的起止时间。
下面一行输入的一个整数m,表示编程兴趣班可选择的时间段。
下列m行,每行都输入两个整数Ai和Bi ,分别表示泽泽参加第i个编程班的起止时间。

输出

输出一个整数,表示两个时间段之间的最长休息时间(如果所有时间段都有冲突,则输出0)。

样例输入输出

输入#1 复制
3
1 5
2 6
2 3
2
2 4
6 8
输出#1 复制
3
输入#2 复制
3
1 5
2 6
3 7
2
2 4
1 4
输出#2 复制
0

提示

【样例解释】
样例1,泽泽可以在这段时间(2,3)参加围棋班,并在另一段时间(6,8)参加编程班。不难算出,在这种情况下,他中间休息的时间是最长的6-3=3。
样例2,他选择任何一段时间,两个兴趣班上课的时间都有冲突,所以答案是0。
【数据范围约定】
对于60%的数据,保证1≤n≤10000,1≤m≤10000
对于100%的数据,保证1≤n≤200000,1≤m≤200000 ,1≤Li≤Ri≤1000000000,1≤Ai≤Bi≤1000000000


序号 标题 作者 发表时间 费用 订购数 操作