Problem Statement
A number of passangers are travelling in a bus along a road. Road is a straight line, and every passenger has its own destination, which is represented as distance in kilometers from the beginning of the road. The bus travels 1 kilometer per minute. The bus can stop at any point of the road, but the stop will take extra T minutes before the stop and T minutes after the stop. For example, if the bus starts at moment 0 and wants to make stops at points 5 and 10, it will stop at point 5 at the moment 5 + T (passengers will be able to leave at this moment), will start from the stop at the moment 5 + 2*T and will stop at point 10 at the moment 10 + 3 * T.
If a passenger left the bus not at his destination, he can reach his destination by legs. For every passenger it takes M minutes to pass 1 kilometer. Given numbers M and T, and a int[] destinations, representing the destinations for all passengers, you are to arrange bus stops to minimize the time when all passengers reach their destinations. Return this time.
Definition
- Class:
- MultipleStops
- Method:
- earliestArrival
- Parameters:
- int[], int, int
- Returns:
- int
- Method signature:
- int earliestArrival(int[] destinations, int T, int M)
- (be sure your method is public)
Notes
- Several passengers may share the same destination.
- Route can be set active only at stops.
Constraints
- T will be between 1 and 20, inclusive.
- destinations will contain between 1 and 12 elements, inclusive. (not sure about this, cause we need 3^12 memory)
- Each element of destinations will be between 0 and T - 1, inclusive.
- taxiRoutes will contain between 1 and 20 elements, inclusive.
- Each element of taxiRoutes will contain a space-delimited list of integers between 0 and T - 1, inclusive.
- Each element of taxiRoutes will contain each number between 0 and T - 1 exactly once.
Examples
No public sample cases were explicitly marked for this problem in the original data.
Back to all problems