"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 &lt; 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 &lt;= maxDeparture; ++i) {
            int count = 0;
            for (Times t : times) {
                if (t.arrival &lt;= i &amp;&amp; t.departure &gt; 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;
        }
    }
}
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 &lt; 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.