DSA problem
Meeting Scheduler
You are given the availability time slots of two people, slots1 and slots2, where each slot is [start, end], and a meeting duration. Return the earliest time interval of length duration during which both people are simultaneously available. If no such slot exists, return an empty array.
Each availability list is independent and unordered. The natural first step is to sort both lists by start time. Once sorted, the problem becomes a classic two-pointer sweep: at any moment we examine the earliest slot of each person and ask whether their overlap is long enough to host the meeting.
The overlap of two intervals [s1, e1] and [s2, e2] is [max(s1, s2), min(e1, e2)]. The overlap exists when max(s1, s2) <= min(e1, e2) and its length is the difference. If that length is at least duration, the earliest valid meeting starts at max(s1, s2) and ends duration units later. Otherwise we discard the slot that ends first (it cannot help us anymore) and advance its pointer.
This sweep visits each slot at most once after sorting, so the dominant cost is sorting at O((m + n) log(m + n)) time and O(1) extra space beyond the sort. The two-pointer pattern is robust against tricky cases: empty lists return empty, and large durations relative to available windows simply exhaust both pointers without finding a fit.
Examples
slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8[60,68]slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12[]slots1 = [[0,100]], slots2 = [[5,15],[30,90]], duration = 30[30,60]Constraints
- 1 <= slots1.length, slots2.length <= 10^4
- slots1[i].length, slots2[i].length == 2
- slots1[i][0] < slots1[i][1]
- slots2[i][0] < slots2[i][1]
- 0 <= slots1[i][j], slots2[i][j] <= 10^9
- 1 <= duration <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.