Free Time
Alice and Bob like to play a lot. Unfortunately, their schedule is a little busy nowadays and they are finding it hard to find mutually common free time.
Given two list of intervals of free times; one of Alice and the other corresponding to Bob, you have to find out the total mutually common free time of Alice and Bob. For each separate list of intervals, it's ensured that the no two intervals in the list intersect each other; however, they may touch each other.
For example, if Alice's list of intervals is { [1, 4], [6, 10], [13, 16] }, that means that she is free for three hours, from t = 1 to t = 4. Similarly, she is free for 4 hours from t = 6 to t = 10. If Bob's list of intervals is { [2, 5], [10, 15] }, then from t = 2 to t = 4, both of them are free, which leads to 2 hours of free time, as well as from t = 13 to t = 15, which is another two hours of mutually common free time. Therefore the total amount of free time is 4.
Input
• The first line of each test case contains two space-separated integers n, m where n denotes the size of interval list of Alice and m denotes that of Bob.
• Each of next n lines contains two space-separated integers si, ei denoting that the i-th interval starts from si and ends at ei.
• Similarly, the next m lines contain the interval list of Bob..
Constraints
• 1 ≤ n, m ≤ 10^5
• 1 ≤ si ≤ ei ≤ 10^9
Sample Input
3 2
1 4
6 10
13 16
2 5
10 15
Sample Output
4
Explanation
The mutually free time is from 2 to 4 and from 13 to 15. So, overall they spend 4 seconds with each other.
Subtasks
• For 30% of the score: 1≤n≤1000, 1≤si≤ei≤10^6
• Remaining 70%: No extra constraints.
Free Time Alice and Bob like to play a lot. Unfortunately, their schedule is a little busy nowadays and they are finding it hard to find mutually common free time. Given two list of intervals of free times; one of Alice and the other corresponding to Bob, you have to find out the total mutually common free time of Alice and Bob. For each separate list of intervals, it's ensured that the no two intervals in the list intersect each other; however, they may touch each other. For example, if Alice's list of intervals is { [1, 4], [6, 10], [13, 16] }, that means that she is free for three hours, from t = 1 to t = 4. Similarly, she is free for 4 hours from t = 6 to t = 10. If Bob's list of intervals is { [2, 5], [10, 15] }, then from t = 2 to t = 4, both of them are free, which leads to 2 hours of free time, as well as from t = 13 to t = 15, which is another two hours of mutually common free time. Therefore the total amount of free time is 4.
Input • The first line of each test case contains two space-separated integers n, m where n denotes the size of interval list of Alice and m denotes that of Bob. • Each of next n lines contains two space-separated integers si, ei denoting that the i-th interval starts from si and ends at ei. • Similarly, the next m lines contain the interval list of Bob.. Constraints • 1 ≤ n, m ≤ 10^5 • 1 ≤ si ≤ ei ≤ 10^9 Sample Input 3 2 1 4 6 10 13 16 2 5 10 15 Sample Output 4 Explanation The mutually free time is from 2 to 4 and from 13 to 15. So, overall they spend 4 seconds with each other.
Subtasks • For 30% of the score: 1≤n≤1000, 1≤si≤ei≤10^6
• Remaining 70%: No extra constraints.