"Parking" challenge solution

Question

This is the problem statement. I have submitted successfully a \$O(n^2)\$ solution and I would like to know if there is a way to improve the running time to, maybe, \$O(n \log n)\$.

Having dropped out of school because of chemistry, Luka got a job driving trucks. One evening he parked his three trucks in a rest area which charges for parking in an unusual way – they give a discount on quantity.

When only one truck is parked, the driver pays AA kuna per minute. When two trucks are parked, the drivers each pay BB kuna per minute. When three trucks are parked, the drivers each pay CC kuna per minute.

Given the numbers AA, BB and CC, as well as the intervals in which Luka’s three trucks are parked, determines how much Luka needs to pay the owner of the rest area.

Input

The first line contains three integers AA, BB and CC (\1ドル \le C \le B \le A \le 100\$), the prices of parking as defined above. Each of the following three lines contains two integers each. These are the arrival and departure times (in minutes) of one of Luka’s trucks. The arrival time will always be earlier than the departure time. All time indexes will be between 1 and 100.

Output

Output the overall cost of Luka’s parking his three trucks.

Current solution (please note that I use custom I/O which I haven't included):

public class Parking {
 public static void main(String[] args) {
 InputReader in = new InputReader(System.in);
 OutputWriter out = new OutputWriter(System.out);
 int A = in.readInt();
 int B = in.readInt();
 int C = in.readInt();
 int minArrival = Integer.MAX_VALUE;
 int maxDeparture = Integer.MIN_VALUE;
 Times[] times = new Times[3];
 for (int i = 0; i < 3; ++i) {
 int arrival = in.readInt();
 int departure = in.readInt();
 minArrival = Math.min(minArrival, arrival);
 maxDeparture = Math.max(maxDeparture, departure);
 times[i] = new Times(arrival, departure);
 }
 int result = 0;
 for (int i = minArrival; i <= maxDeparture; ++i) {
 int count = 0;
 for (Times t : times) {
 if (t.arrival <= i && t.departure > i) {
 count++;
 }
 }
 switch (count) {
 case 1:
 result += A;
 break;
 case 2:
 result += B * 2;
 break;
 case 3:
 result += C * 3;
 break;
 default:
 break;
 }
 }
 out.print(result);
 out.close();
 }
 private static class Times {
 final int arrival;
 final int departure;
 Times(int arrival, int departure) {
 this.arrival = arrival;
 this.departure = departure;
 }
 }
}

• Pimgd: mind including the problem description in your question?
• Orestis: I have added the description of the problem at the end of the question. Thanks.

Answer 1

If you turn the arrival and departure times into objects that give +1 or -1 to a truckCounter variable, then sort this array (\$O(n log(n))\$), then you can iterate over the list of events.

As a result, you'll have 6 iterations after sorting, and the algorithm will bound on not the length of the durations but the amount of trucks.

So read inputs, sort the array, and then...

//assuming there is an array "sortedTruckEvents" of type TruckEvent containing an object which has
//getModifier as -1 for truck leaving and +1 for truck arriving
//and getTime for retrieving when this happens
//and assuming there is an array "prices" containing 0 at index 0, priceA * 1 at index 1, priceB * 2 at index 2, priceC * 3 at index 3
int result = 0;
int truckCounter = 0;
int currentTime = 0;
for(int i = 0; i < sortedTruckEvents.length; i++) {
 TruckEvent event = sortedTruckEvents[i];
 result += prices[truckCounter] * (event.getTime() - currentTime);
 truckCounter += event.getModifier();
 currentTime = event.getTime();
}
//now result contains the total price

It's as easy as that.

The trick here is to realize that the points of interest in this case is where things change. And the problem variables don't change per timestep; they change per truck arrival and departure.

The problem has even made it easy for you by guaranteeing all the trucks will arrive before they leave and that the trucks will leave at all.

• Orestis: It is not clear to me what getTime should return. Could you please elaborate a little bit more? Do you mean the actual value ?
• Pimgd: getTime would return either the arrival time or the department time. Looking at the example, if you get 15 70, then you'd have one TruckEvent with a modifier of +1 and a time of 15, and one TruckEvent with a modifier of -1 and a time of 70. The TruckEvents are then sorted on the time variable.
• Orestis: It doesnt seem to work for the sample inputs. I have uploaded the code here pastebin.com/5Yn0G2bu if you have the time and energy to take a look. Sorry about the external link but the class is quite big to post it as a comment here. Advice if that's not proper.
• Pimgd: @Orestis prices[truckCounter] * event.getValue() - currentTime; is wrong, I have fixed it in the code in my answer. It needs parentheses around the time difference calculation. Thanks for spotting that mistake.