UVA - 12694 - Meeting Room Arrangement

This article will explain my thought process to solve a problem called Meeting Room Arrangement (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Dynamic Programming

Objective

Given:

List of event schedules

We want to:

Find the maximum amount of events that can be scheduled.

Glossary

Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Longest Increasing Subsequence (LIS) — A problem of finding the longest possible subsequence where the elements are sorted in strictly increasing order.

Observation

Each event has a start and finish time, and we want to find the longest sequence of events that does not overlap, meaning the start time of an event must be greater or equals to the finish time of the previous event. By definition, this is similar to LIS problem, although the start and end time isn’t strictly increasing. Since this is a variation of LIS problem, it should give us a hint that it can be solved with DP.

Next, we want to transform the problem into LIS problem. By sorting the events using the start time, we could say that we want to find a subsequence with increasing schedule (the previous finish time greater than or equals the next start time).

After that, we want to breakdown the problem to solve it with DP. After an event is finished, any following events with greater than or equals start time can use the meeting room. This means, what we want to do is finding the maximum amount of events that can happens before a certain time. By iteratively doing this, we will eventually find the maximum amount of events in a day. At each iteration, use the event start time to get the maximum amount of events before the event started, and increment it for the number of events when the event finished.

Algorithm

The DP can be stored in a 1 dimension array, with time as the state and maximum number of events as the value. After that, we can use bottom-up approach to find the maximum number of events before each time. This is done by iteratively going from the minimum time (zero) until the maximum time, as the cutoff for the start time. Using priority queue, events with the least start time can can be added into the subsequence as long as the start time is less than or equals the cutoff time.

The time complexity of this solution is O({maximum finish time} * {total events}) or O(10^3).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 12694 - Meeting Room Arrangement
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4432
 */
public class Main {
    private static final int[] LAST_EVENT = new int[]{0, 0};

    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalCases = in.nextInt();
        for (int i = 0; i < totalCases; i++) {
            final LinkedList<int[]> events = new LinkedList<>();
            while (true) {
                final int[] event = new int[]{in.nextInt(), in.nextInt()};
                final boolean isEOF = Arrays.equals(LAST_EVENT, event);
                if (isEOF) break;
                events.addLast(event);
            }

            final Input input = new Input();
            input.events = events.toArray(new int[0][0]);

            final Output output = process.process(input);
            out.println(output.totalEvents);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int[][] events;
}

class Output {
    public int totalEvents;
}

class Process {
    private static final Comparator<int[]> ORDER_BY_START_AND_FINISH = Comparator
        .comparingInt((int[] e) -> e[0])
        .thenComparingInt((int[] e) -> e[1]);

    public Output process(final Input input) {
        final int[][] events = input.events;

        final int maxFinishTime = getMaxFinishTime(events);
        final int[] totalEventsPerTime = new int[maxFinishTime + 1];

        final PriorityQueue<int[]> queue = new PriorityQueue<>(ORDER_BY_START_AND_FINISH);
        queue.addAll(Arrays.asList(events));

        for (int time = 0; time <= maxFinishTime; time++) {
            if (time > 0) {
                totalEventsPerTime[time] = Math.max(
                    totalEventsPerTime[time],
                    totalEventsPerTime[time - 1]
                );
            }

            while (!queue.isEmpty()) {
                final int[] event = queue.peek();
                final int startTime = event[0], finishTime = event[1];
                if (startTime > time) break;

                totalEventsPerTime[finishTime] = Math.max(totalEventsPerTime[finishTime], totalEventsPerTime[startTime] + 1);
                queue.remove();
            }
        }

        final Output output = new Output();
        output.totalEvents = totalEventsPerTime[maxFinishTime];
        return output;
    }

    private int getMaxFinishTime(final int[][] events) {
        int max = 0;
        for (int[] event : events) {
            max = Math.max(max, event[1]);
        }
        return max;
    }
}