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;
            }
        }
    }

Subsets

Question: Find all subsets of the set {‘foo’, ‘bar’, baz’}.  The method signature for the solution should be

public List<HashSet<String>> findSubsets(Set<String> input)

Evaluation: There is a fairly clever way to solve this that will run in O(2^n) which by the way is the fastest solution available for this question.  There is a more obvious but also slower solution that runs in something more like O((2^n)^2).

To get to the faster version of the solution consider how many subsets there are.  The naive solution comes from the recognition that if you start with the empty set {} and then for each element in the list of sets so far you create 1 new set for every existing set by adding the new element to every existing set.

-> {}

-> {‘foo’}

-> {‘bar’}, {‘foo’, ‘bar’}

-> {‘baz’}, {‘foo’, ‘baz’}, {‘bar’, ‘baz’}, {‘foo’, ‘bar’, ‘baz’}

When you put all of these together there are a total of 8 subsets.  The key here is to recognize that there are 2^n subsets in the solution.  The next thing to remember is that 2^n is binary.  Now, try counting from 0-2^n in binary (in this case 0-8).

000

001

010

011

100

101

110

111

Do you see a solution emerging?  If you take the binary representation of every number from 0 – 2^n you get 1 unique set at each index.

Code:

public List<HashSet<String>> findSubsets(Set<String> input) {
        LinkedList<HashSet<String>> result = new LinkedList<HashSet<String>>();
        LinkedList<String> list = new LinkedList<String>();
        list.addAll(input);
        int numsubsets = (int)Math.pow(2, input.size());
        for(int i=0;i<numsubsets;i++) {
            int current = i;
            int index = 0;
            HashSet set = new HashSet();
            result.add(set);
            while(current != 0) {
                if(current % 2 !=0) {
                    set.add(list.get(index));
                }
                index++;
                current = current >>> 1;
            }
        }

        return result;
    }