(UVA) Dragon of Loowater - Solution

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

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

We need an array to keep the diameters of the dragon's head, and another one to keep the knights' heights. Then, we sort both arrays, and for every knight, we check if he can cut a dragon's head. In the end, we only need to see if all the heads were cut, and give the answer according to it.


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 numHeads = sc.nextInt();
        int numKnights = sc.nextInt();
        while (numHeads != 0 || numKnights != 0) {
            int[] heads = new int[numHeads];
            int[] knightsHeights = new int[numKnights];
            for (int i = 0; i < numHeads; i++) {
                heads[i] = sc.nextInt();
            }
            for (int i = 0; i < numKnights; i++) {
                knightsHeights[i] = sc.nextInt();
            }
            Arrays.sort(heads);
            Arrays.sort(knightsHeights);
           
            int gold = 0;
            int cut = 0;
            int indexH = 0;
            for (int i = 0; i < numKnights; i++) {
                if (knightsHeights[i] < heads[indexH]) {
                    continue;
                }
                cut++;
                gold += knightsHeights[i];
                indexH++;
                if (indexH >= numHeads) {
                    break;
                }
            }
           
            if (cut == numHeads) {
                bw.write(gold+"\n");
            } else {
                bw.write("Loowater is doomed!\n");
            }
           
            numHeads = sc.nextInt();
            numKnights = 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);
    }
}