Conflicting Appointments

Question: Write a program to find conflicts in a list of appointments.  Let’s say that you are writing a calendar program and you need a method to find conflicting meetings on the schedule.

You have a class

class Appointment {
        long start;
        long end;
        boolean hasConflict = false;
    }

The method signature should look like

public void findConflicts(List<Appointment> appts)

So say that your meetings look something like the following

|------------|
                   |---------------|
                        |----------------|

The first meeting doesn’t conflict with any other meetings. The second and third meeting overlap so in the result set hasConflict will be false for the first appointment and true for the second and third.

Evaluation:  A naive solution to this problem would be to evaluate every appointment against all other appointments.  So take the 1st appointment and compare it to 2, 3.  Take the 2nd appointment and compare it to 1, 3.  Etc.  Of course the running time here is O(n^2) so this is no good.

An optimal solution is to first sort the appointments by their start time.  Quicksort will give us a running time of O(n log n).  Once the appointments are sorted we just need to make sure that for each appointment, it doesn’t start before whatever the latest appointment was so far.  So we just iterate through each appointment keeping track of the appointment with the latest end time.  For each appointment we check to see if the meeting starts before that latest meeting ends.

Code:

public void findConflicts(List<Appointment> appts) {
        Appointment latest = null;
        Iterator<Appointment> iter = appts.iterator();
        while(iter.hasNext()) {
            Appointment next = iter.next();
            if(latest != null && next.start < latest.end) {
                next.hasConflict = true;
                latest.hasConflict = true;
            }

            if(latest == null || next.end > latest.end) {
                latest = next;
            }
        }
    }