As Far As It Takes Me
Vicky has embarked on a tour where he travels only by buses running over small distances. In general there are n buses all going in the same direction, with the ith bus starting at (xi – 1) km from his starting point and running upto yi km from his starting point covering (yi – xi + 1) km. The buses do not stop anywhere in between so Vicky cannot switch buses while in the middle of a bus journey. Neither does he go back from where a bus has dropped him to catch another bus whose starting location might have been left behind his current location. He must walk from where the previous bus has dropped him to the location where the next bus he intends to catch starts.
Vicky wants to travel as much distance as possible through these buses no matter how long does this tour of him takes him. Given the starting and the finishing location of buses, help Vicky choose the buses that will ensure he travels the maximum distance on the chosen set of buses. The starting point is obviously taken as 0 km.
The first line consist of number of test cases T, followed by a blank line, followed by T test cases each separated from the previous one by a blank line. The first line of each test case consist of a single number n – the number of bus services, followed by n lines where the ith line contains two space separated integer xi and yi, such that the ith bus starts at a distance (xi – 1) km from his starting point and travels upto yi km from his starting point.
For each test case print the maximum distance Vickey can travel through these buses on a separate line.
1 <= T <= 2
1 <= n <= 10000
1 <= xi <= yi <= 100000000
Input: 1 3 1 4 2 6 6 8 Output: 7 Explanation:
Vicky can travel maximum distance by taking buses 1st and 3rd , covering a total of (4 – 1 + 1) +
(8 – 6 + 1) = 7 km. Had he taken the first 2nd bus he could have travelled (6 – 2 + 1) = 5km.
|Time Limit:||0.182573 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, GO|
Fetching successful submissions