Problem Link - Wormholes
Problem Statement
The year is 2012 and today is the day of ZCO. This year there are N contests and the starting and ending times of each contest is known to you. You have to participate in exactly one of these contests. Different contests may overlap. The duration of different contests might be different.
There is only one examination centre. There is a wormhole V that transports you from your house to the examination centre and another wormhole W that transports you from the examination centre back to your house. Obviously, transportation through a wormhole does not take any time; it is instantaneous. But the wormholes can be used at only certain fixed times, and these are known to you.
So, you use a V wormhole to reach the exam centre, possibly wait for some time before the next contest begins, take part in the contest, possibly wait for some more time and then use a W wormhole to return back home. If you leave through a V wormhole at time t 1 and come back through a W wormhole at time t 2, then the total time you have spent is (t 2 - t 1 + 1). Your aim is to spend as little time as possible overall while ensuring that you take part in one of the contests.
You can reach the centre exactly at the starting time of the contest, if possible. And you can leave the examination centre the very second the contest ends, if possible. You can assume that you will always be able to attend at least one contest–that is, there will always be a contest such that there is a V wormhole before it and a W wormhole after it.
For instance, suppose there are 3 contests with (start,end) times (15,21), (5,10), and (7,25), respectively. Suppose the V wormhole is available at times 4, 14, 25, 2 and the W wormhole is available at times 13 and 21. In this case, you can leave by the V wormhole at time 14, take part in the contest from time 15 to 21, and then use the W wormhole at time 21 to get back home. Therefore the time you have spent is (21 - 14 + 1) = 8. You can check that you cannot do better than this.
Approach
The idea is to determine the smallest total time spent for participating in one contest. To do this, first, sort the V and W wormhole times. For each contest, the aim is to find:
-
The largest wormhole time in V that is less than or equal to the contest’s start time. This ensures you can arrive just in time or earlier for the contest.
-
The smallest wormhole time in W that is greater than or equal to the contest’s end time. This ensures you can leave immediately after the contest ends.
Using binary search, find the appropriate times from V and W for each contest. If both suitable times are found, calculate the total time as w[k] - v[j] + 1. Keep track of the minimum time across all contests. Output this minimum as the result.
Time Complexity
Sorting V and W takes O(x \log x + y \log y), and finding the times for N contests takes O(n \log x + n \log y). The overall complexity is O((x + y) \log(x + y) + n \log(x + y)).
Space Complexity
The space complexity is O(x + y + n) for storing wormhole times and contest intervals.