# Find overlapping appointments

**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 time and search . Extra space required is .

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