(SPOJ) Dentista - Solution

Link to the problem: http://br.spoj.com/problems/JDENTIST/

The solution below keeps the appointments in an array. Next, we sort it by the end of each appointment. Then, we pass through the array checking the next possible appointment to schedule.


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

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        int numAppointments = Integer.parseInt(line);
        Appointment[] appointments = new Appointment[numAppointments];
        for (int i = 0; i < numAppointments; i++) {
            line = br.readLine();
            String[] s = line.split(" ");
            appointments[i] = new Appointment(Integer.parseInt(s[0]), Integer.parseInt(s[1]));     
        }
        Arrays.sort(appointments);
       
        int count = 1;
        int previousEndTime = appointments[0].end;
        for (int i = 1; i < numAppointments; i++) {
            if (appointments[i].start >= previousEndTime) {
                previousEndTime = appointments[i].end;
                count++;
            }
        }
           
        bw.write(count+"\n");
       
        br.close();
        bw.flush();
        bw.close();
        
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Appointment implements Comparable<Appointment> {
    int start;
    int end;
   
    public Appointment(int s, int e) {
        start = s;
        end = e;
    }
   
    public int compareTo(Appointment a) {
        return this.end-a.end;
    }
}