⚡Flashcard Drill➔
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

  1. Two pointers, one per list. Compute the intersection of the current pair: start = max(starts), end = min(ends).
  2. If the intersection is at least duration long, it is a candidate; track the one with the smallest start.
  3. Then advance the pointer whose slot ends earlier, since that slot cannot overlap anything further in the other list.
  4. 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 is start + 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 exactly duration is valid.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems