Meeting Scheduler
Understanding the Problem
We have two people, each with a list of time slots when they are free. We need to find the earliest window of at least duration minutes where both are simultaneously available.
A valid meeting window must lie within the overlap of one slot from person 1 and one slot from person 2. The problem reduces to finding overlapping pairs of slots, computing each overlap length, and returning the earliest overlap that is at least duration long.
The overlap of two slots [s1, e1] and [s2, e2] is [max(s1, s2), min(e1, e2)]. Its length is min(e1, e2) - max(s1, s2), which is positive only when the slots intersect. The slots are not given in sorted order, and each person's own slots never overlap each other. That structure (two lists of disjoint intervals) lets us avoid comparing every pair once both lists are sorted.
Key Constraints:
1 <= slots1.length, slots2.length <= 10^4→ With up to 10,000 slots per person, an O(n m) brute force reaches 10^4 10^4 = 10^8 overlap checks, which is slow. Sorting plus a linear scan is O(n log n + m log m), which is comfortable here.0 <= slots1[i][0] < slots1[i][1] <= 10^9→ Time values reach a billion, so indexing an array by time value is not an option. We work with the intervals directly. The values still fit in a 32-bit signed integer, andstart + durationreaches at most 10^9 + 10^6, which also fits, so no overflow guard is needed.
Approach 1: Brute Force (Check All Pairs)
Intuition
Try every combination of one slot from person 1 and one slot from person 2. For each pair, compute the overlap. If the overlap is at least duration long, it can host the meeting, so record it as a candidate. After checking all pairs, return the candidate with the earliest start time.
This checks every pair regardless of whether they could intersect, which is slow for large inputs, but it is simple and serves as a correctness baseline.
Algorithm
- Initialize
resultas an empty list to track the best answer so far. - For each slot
s1inslots1: - For each slot
s2inslots2: - Compute the overlap:
overlapStart = max(s1[0], s2[0]),overlapEnd = min(s1[1], s2[1]). - If
overlapEnd - overlapStart >= duration, this pair can host the meeting. - If
resultis empty oroverlapStartis earlier than the current best, updateresult = [overlapStart, overlapStart + duration]. - Return
result.
Visualization and Code
Loading animation...
- Time Complexity: O(n m). We check every pair of slots, one from each person. With n slots in slots1 and m slots in slots2, that's n m overlap computations.
- Space Complexity: O(1). We only store the current best result, no extra data structures needed.
The next approach processes the slots in chronological order so it only compares slots that are near each other in time, which removes the quadratic blowup.
Approach 2: Sort + Two Pointers
Intuition
Sort both slot lists by start time, then walk through them with two pointers, the same way you merge two sorted arrays. At each step, compare the current slot from each list, compute their overlap, and check whether it is at least duration long. If it is, that is the answer. If not, advance the pointer whose slot ends earlier.
Two questions need answers: why is advancing the earlier-ending slot safe, and why is the first match the earliest possible meeting?
Say slots1[i] ends before slots2[j]. Every slot after slots2[j] starts at or after slots2[j]'s start, so it starts at least as late and cannot share more time with slots1[i] than slots2[j] already does. Since slots1[i] paired with slots2[j] was too short, slots1[i] cannot satisfy duration against any later slot either, so discarding it loses no answer.
The earliest-match claim follows from processing slots in increasing start order: the first overlap that reaches duration begins no later than any overlap found afterward, so it is the earliest valid meeting time.
Algorithm
- Sort
slots1by start time. - Sort
slots2by start time. - Initialize two pointers
i = 0andj = 0. - While
i < slots1.lengthandj < slots2.length: - Compute
overlapStart = max(slots1[i][0], slots2[j][0]). - Compute
overlapEnd = min(slots1[i][1], slots2[j][1]). - If
overlapEnd - overlapStart >= duration, return[overlapStart, overlapStart + duration]. - Otherwise, advance the pointer whose current slot ends earlier. If
slots1[i][1] < slots2[j][1], incrementi. Otherwise, incrementj. - If no valid overlap was found, return an empty list.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n + m log m). Sorting takes O(n log n) and O(m log m) for the two lists. The two-pointer pass is O(n + m). The sorting dominates.
- Space Complexity: O(1) extra space beyond sorting. The two-pointer pass itself uses constant extra space. Some languages use O(n) space for their sort.
The two-pointer approach has the best time complexity for this problem. A common alternative merges both lists into a single sorted sequence and scans neighbors, which trades a little extra space for not having to track two pointers.
Approach 3: Heap-Based (Min-Heap on Start Time)
Intuition
Combine all slots from both people into one min-heap ordered by start time, dropping any slot shorter than duration because it can never host the meeting on its own. Then pull slots off the heap in order and compare each one with the previous slot.
If a slot prev and the next slot curr overlap by at least duration, that overlap is the answer. The two slots must come from different people: a single person's slots are disjoint, so two same-person slots in sorted order satisfy prev[1] < curr[0], which can never give a positive overlap. The first qualifying neighbor pair therefore gives a valid cross-person meeting, and because the heap yields slots in increasing start order, it is the earliest one.
Algorithm
- Create a min-heap (priority queue) ordered by start time.
- Add all slots from both lists to the heap, but skip any slot where
end - start < duration. - Pull the first slot off the heap. Call it
prev. - While the heap is not empty:
- Pull the next slot
currfrom the heap. - If
prev[1] >= curr[0] + duration, return[curr[0], curr[0] + duration]. - Set
prev = curr. - If no valid overlap found, return an empty list.
Visualization and Code
Loading animation...
- Time Complexity: O((n + m) log(n + m)). Building the heap takes O(n + m) insertions, each O(log(n + m)). Extracting all elements is the same. Similar to sorting but with slightly larger constant factor due to heap operations.
- Space Complexity: O(n + m). The heap stores up to n + m slots.