"Parking" challenge solution

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 i) {
count++;
}
}

switch (count) {
case 1:
result += A;
break;
case 2:

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.

StackExchange Code Review Q#134438, answer score: 6