(UVA) The Bus Driver Problem - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2384

The solution below used a Greedy approach to solve this problem.

We sort the array related to the morning routes in ascending order, and the array related to the evening routes in descending order. Then, it is possible to have the best solution once we have the sum of the biggest value in an array and the smallest value in the other.


import java.io.*;
import java.util.*;

class Main {
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numBusDrivers = sc.nextInt();
        int limit = sc.nextInt();
        int r = sc.nextInt();
        while (numBusDrivers != 0 || limit != 0 || r != 0) {
            Integer[] morning = new Integer[numBusDrivers];
            for (int i = 0; i < numBusDrivers; i++) {
                morning[i] = sc.nextInt();
            }
           
            Integer[] evening = new Integer[numBusDrivers];
            for (int i = 0; i < numBusDrivers; i++) {
                evening[i] = sc.nextInt();
            }
           
            Arrays.sort(morning);
            Arrays.sort(evening, Collections.reverseOrder());
           
            int extraHours = 0;
            for (int i = 0; i < numBusDrivers; i++) {
                int workedTime = morning[i]+evening[i];
                if (workedTime > limit) {
                    extraHours += (workedTime-limit);
                }
            }
            bw.write((extraHours*r)+"\n");
                       
            numBusDrivers = sc.nextInt();
            limit = sc.nextInt();
            r = sc.nextInt();
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}