Problem Statement |
| |
You have a very important meeting to attend, and you don't want to be late for it. You are currently at coordinate 0, and the meeting is being held at coordinate D (in meters) in T seconds. Unfortunately, there are a number of traffic lights between you and your destination.
The i-th element of lights describes a single traffic light and is formatted as "a b pos" (quotes for clarity). pos is the coordinate of the light (in meters), and the numbers a and b describe the light's behavior. Starting at time 0, the light is red for a seconds, then green for the next b seconds, then red for the next a seconds, and so on. In other words, between time 0 (inclusive) and time a (exclusive), the light is red, between time a (inclusive) and time a+b (exclusive), it is green, between time a+b (inclusive) to 2*a+b (exclusive), it is red again, and so on. If you arrive at a traffic light when it is red, you cannot pass until it becomes green (otherwise, you would get a ticket). For example, if you arrive at a traffic light where a = 3 and b = 4, you cannot pass at times 0, 1.5 or 7, but you can pass at times 3, 5.33 or 6.99.
You must get to your meeting in T seconds or less, and to reduce your risk of getting a speeding ticket, you must do so while minimizing your maximum speed along the way. Return this maximum speed (in meters per second). If it is not possible to arrive on time, return -1 instead.
|
| |
Definition |
| | | Class: | SafeDrive | | Method: | minSpeed | | Parameters: | String[], int, int | | Returns: | double | | Method signature: | double minSpeed(String[] lights, int T, int D) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The return value is actually the infimum of the set of all possible maximum speeds that allow you to arrive at the meeting on time. |
| - | The returned value must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | lights will contain between 0 and 50 elements, inclusive. |
| - | Each element of lights will contain between 5 and 50 characters, inclusive. |
| - | Each element of lights will be formatted as "a b pos" (quotes for clarity), where a, b and pos are each integers between 1 and 1,000,000,000, inclusive, with no leading zeroes. |
| - | There will be no traffic light at position D. |
| - | No two traffic lights will be at the same position. |
| - | T will be between 1 and 1,000,000,000, inclusive. |
| - | D will be between 1 and 1,000,000,000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 1.0 | | If you drive at a constant speed of one meter per second, you will arrive at the only traffic light at time 3. The light becomes green at exactly this time, so you can pass without stopping. |
|
|
| 1) | |
| | | Returns: 1.0 | | In this case, if you drove at a constant speed of one meter per second, you would arrive at the traffic light at time 7, when the light switched to red. You would then have to wait three seconds for it to turn green, and you would end up being late. Therefore, you must drive just a little faster, so you can catch the light while it's green. Note that this speed is arbitrarily close to 1.0, however, and a return of 1.0 is correct. |
|
|
| 2) | |
| | | Returns: 1.7500000000000004 | | It is of no use to drive faster than one meter per second until you reach the first traffic light. Then you have two options. The first one is to drive fast enough to reach the second light while it is still green, with a speed just a little over 2.33 meters per second. After you pass the traffic light, a speed of one meter per second is enough to arrive at the meeting on time. The other option is to drive slower, say with a speed of 1.16 meters per second, and reach the second traffic light at time 8. Then you would have to drive at a speed of 1.75 meters per second to arrive just in time for the meeting. Clearly, the better choice is the second one, where the maximum speed is 1.75 as opposed to approximately 2.33 in the first case. |
|
|
| 3) | |
| | {"1 2 3", "2 2 5", "3 3 7", "1 6 9", "3 4 11"} | 12 | 13 |
| Returns: 1.25 | |
|
| 4) | |
| | {"2 2 6", "4 5 3", "3 2 8"} | 7 | 10 |
| Returns: -1.0 | | Unfortunately, there is at least one red light at every moment of time left until the meeting, so you can't make it. |
|
|
| 5) | |
| | {"99 190 2723", "239 138 6411", "262 235 2509", "62 60 6494",
"16 70 4938", "70 59 4701", "172 165 5118", "16 256 7816",
"31 40 213", "189 183 1955", "186 11 4485", "175 281 9816",
"152 242 8116", "180 11 5899", "274 189 3978"} | 695 | 5323 |
| Returns: 9.728682170542637 | |
|