NeetCode #214LC-1229MediumTwo Pointers
← Back to All Problems#214 · #1229 · Meeting Scheduler(安排会议日程)
📌 Problem Statement & Constraints
Given the availability time slots of two people as
slots1 and slots2, and a meeting duration, return the earliest time slot that works for both and has the required duration. If no such slot exists, return an empty array. Constraints: 1 <= slots1.length, slots2.length <= 10^4, slots within each list are disjoint and sorted by start.💡 Core Algorithmic Approaches
- Two pointers, one per list. Compute the intersection of the current pair:
start = max(starts),end = min(ends). - If the intersection is at least
durationlong, it is a candidate; track the one with the smallest start. - Then advance the pointer whose slot ends earlier, since that slot cannot overlap anything further in the other list.
- Return the best candidate found, or an empty array.
💻 Benchmark Python3 Implementation
class Solution:
def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
i = j = 0
best = None
while i < len(slots1) and j < len(slots2):
start = max(slots1[i][0], slots2[j][0])
end = min(slots1[i][1], slots2[j][1])
if end - start >= duration:
if best is None or start < best[0]:
best = [start, start + duration] # only the first `duration` units
# advance the slot that ends earlier
if slots1[i][1] < slots2[j][1]:
i += 1
else:
j += 1
return best if best else []⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m + n): each pointer advances monotonically.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Returning
[start, end]instead of[start, start + duration]: the answer is the earliest slot of exactly the requested duration, so the end isstart + duration. - Returning the first overlap found: it may not have the smallest start; track the minimum explicitly.
- Advancing both pointers on an overlap: the slot that ends earlier still cannot overlap later slots of the other list, so it is the one to advance -- but only one pointer should move per iteration.
- Using
>instead of>=for the duration check: a slot of exactlydurationis valid.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.