Meeting Scheduler

Meeting Scheduler

What is this problem about?

The "Meeting Scheduler" interview question typically asks you to find a common available time slot of a specific duration between two people, given their individual schedules. Each person's schedule is represented as a list of time intervals indicating their busy periods. The goal is to find any time slot (or the earliest one) of at least a specified duration that is free for both individuals. This problem is a practical application of interval manipulation, requiring you to identify overlaps in busy times to deduce free times. It's a common scenario in calendar applications and resource allocation.

Why is this asked in interviews?

This "Meeting Scheduler" coding problem is frequently asked in technical interviews at companies like Uber, Google, and Amazon because it effectively evaluates a candidate's ability to handle intervals, apply sorting algorithms, and use the Two Pointers technique efficiently. It's a pragmatic problem that mirrors real-world challenges in calendar management or system design. Interviewers use this to assess logical reasoning, efficiency in handling time-based data, and the ability to combine multiple algorithmic patterns for an optimal solution. Success demonstrates strong foundational knowledge and practical problem-solving skills.

Algorithmic pattern used

The most efficient algorithmic pattern for the "Meeting Scheduler" interview question involves Sorting followed by a Two Pointers approach.

1. Sort Schedules: First, ensure both individuals' busy schedules are sorted by their start times.
2. Merge Busy Intervals (Implicitly or Explicitly): You can either explicitly merge the busy intervals of both people to find their combined busy schedule, or more efficiently, use two pointers to iterate through both sorted schedules simultaneously.
3. Identify Free Slots: As you iterate with two pointers (one for each person's schedule), focus on the "gap" between their busy intervals.
   • Maintain the intersection of the current busy intervals of both people.
   • The free slot would be derived from the non-overlapping parts or when both are free after a busy period.
   • A simpler approach involves iterating through both schedules and for each pair of intervals (one from each person), calculate their overlap. If there's an overlap, the duration of their mutual free time before the next interval is considered.

A refined two-pointer strategy:

• Sort both slots1 and slots2.
• Use two pointers, p1 and p2, initialized to 0.
• In each step, find the intersection of slots1[p1] and slots2[p2].
  • start = max(slots1[p1].start, slots2[p2].start)
  • end = min(slots1[p1].end, slots2[p2].end)
• If end - start >= duration, then [start, start + duration] is a valid answer.
• Advance the pointer corresponding to the interval that finishes earlier.

Example explanation

Let slots1 = [[10, 50], [60, 120], [140, 210]] and slots2 = [[0, 15], [60, 70]], duration = 8.

Both schedules are already sorted. p1 = 0, p2 = 0.

1. slots1[0] = [10, 50], slots2[0] = [0, 15] start = max(10, 0) = 10 end = min(50, 15) = 15 Overlap is [10, 15]. end - start = 5. 5 < duration (8). No valid slot. slots2[0] ends earlier (15 < 50), so p2 increments. p2 = 1.

2. slots1[0] = [10, 50], slots2[1] = [60, 70] start = max(10, 60) = 60 end = min(50, 70) = 50 Overlap: start > end, so no overlap. slots1[0] ends earlier (50 < 70), so p1 increments. p1 = 1.

3. slots1[1] = [60, 120], slots2[1] = [60, 70] start = max(60, 60) = 60 end = min(120, 70) = 70 Overlap is [60, 70]. end - start = 10. 10 >= duration (8). Found a valid slot! Return [60, 60 + 8] = [60, 68].

Common mistakes candidates make

A common mistake in the "Meeting Scheduler" interview question is failing to sort the input schedules, which is a prerequisite for the efficient two-pointer approach. Another pitfall is incorrectly calculating the overlap between two intervals, leading to misidentified common busy periods or free slots. Candidates might also struggle with handling edge cases where intervals are adjacent or one interval fully contains another. Overcomplicating the logic by trying to generate all free slots before checking their duration, instead of finding the first suitable one, can lead to less efficient solutions.

Interview preparation tip

To master the Meeting Scheduler coding problem, focus on interval problems, sorting, and the Two Pointers technique. Practice merging or finding overlaps between intervals. Understand how to correctly calculate the start and end of an intersection between two intervals: max(start1, start2) for the intersection start, and min(end1, end2) for the intersection end. Work through examples by hand with two pointers moving across the sorted schedules. Pay attention to how to advance the pointers (always advance the pointer of the interval that ends earlier). This problem is an excellent way to practice managing multiple ordered sequences simultaneously.