Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Find overlapping appointments

Sharing is caring!

Problem statement
Given two unsorted arrays, one with event start times and one with end times, find out if any two events overlap.

Solution

The key to the solution is to sort the appointments according to their start time in decreasing order, while keeping the correlation between the start and end time. We then traverse the start/end time arrays and do the following:
– If current appointment is not first appointment and it overlaps with previous appointment return true

Sorting takes \mathcal{O}(n \log n) time and search \mathcal{O}(n). Extra space required is \mathcal{O}(1).

Full code

package problems;

public class OverlappingAppointments {
    private static void quicksort(int[] s, int[] e, int low, int high) {
        if (low < high) {
            int pivot = partition(s, e, low, high);
            quicksort(s, e, low, pivot - 1);
            quicksort(s, e, pivot + 1, high);
        }
    }

    /**
     * Returns index of pivot element
     */
    private static int partition(int[] s, int[] e, int low, int high) {
        int pivot = s[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (s[j] >= pivot) {
                swap(s, j, i);
                swap(e, j, i);
                i++;
            }
        }

        swap(s, i, high);
        swap(e, i, high);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static boolean overlap(int[] s, int[] e) {
        // Sort all appointments in decreasing order of start time.
        quicksort(s, e, 0, s.length - 1);

        for (int i = 1; i < s.length; i++) {
            System.out.print(s[i] + "-" + e[i] + "  ");
            if (e[i] >= s[i - 1]) {
                // overlap
                return true;
            }
        }

        // no overlap
        return false;
    }

    public static void main(String[] args) {
        System.out.println(overlap(new int[] { 2, 4, 29, 10, 22 }, new int[] { 5, 7, 34, 11, 36 }));
    }
}