(UVA) Gas Stations - Solution

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

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

We need to create an array with some information about the gas stations. This array is sorted based on the left limit, and we always try to choose the gas station that covers a bigger right area.


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

class Main {
    public int lengthRoad;
    public int numGasStation;
    public Gas[] gas;
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        lengthRoad = sc.nextInt();
        numGasStation = sc.nextInt();
        while (lengthRoad != 0 || numGasStation != 0) {
            gas = new Gas[numGasStation];
            // read the information about the gas stations
            for (int i = 0; i < numGasStation; i++) {
                int x = sc.nextInt();
                int radius = sc.nextInt();
                gas[i] = new Gas(radius, x-radius, x+radius);
            }
            Arrays.sort(gas); // sort by the left limit

            boolean problem = false;
           
            int numUsedGas = 0;
            int index = 0; // index of the gas station being considered
            int target = 0; // the limit where my left limit can begin
            Gas curr = gas[index];
            if (curr.left > 0) { // there is a space not covered by gas station in the beginning
                problem = true;
            }
            // it is not going to enter in the while
            if (index == 0 && curr.right >= lengthRoad) {
                numUsedGas++;
            }
            while (!problem && curr.right < lengthRoad) {
                int maxReach = curr.right; // I want to choose the gas station that covers more to the right
                // if there is a space between my current gas station and the next one: problem
                if (index+1 < numGasStation && gas[index+1].left > curr.right) {
                    problem = true;
                }
                // decide which gas I am going to use
                while (index+1 < numGasStation && gas[index+1].left <= target) {
                    if (gas[index+1].right > maxReach) {
                        maxReach = gas[index+1].right;
                        curr = gas[index+1];
                    }
                    index++;
                }
                numUsedGas++; // I used the gas chosen previously
                target = curr.right;
                // if I am in the last gas station and it does not cover until the end of the road: problem
                if (index == numGasStation-1 && curr.right < lengthRoad) {
                    problem = true;
                }
            }
           
            if (problem) {
                bw.write("-1\n");
            }
            else {
                bw.write((numGasStation-numUsedGas)+"\n");
            }
           
            lengthRoad = sc.nextInt();
            numGasStation = 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);
    }
}

class Gas implements Comparable<Gas> {
    int radius;
    int left;
    int right;
   
    public Gas(int radius, int left, int right) {
        this.radius = radius;
        this.left = left;
        this.right = right;
    }
   
    public int compareTo(Gas g) {
        return this.left-g.left;
    }
}