Calendar Matching

Tags

Calendar Matching

Category

Arrays

Difficulty

Very Hard

Problem Statement

Given two people's calendars (lists of booked meeting intervals), their daily bounds (earliest and latest available times), and a desired meeting duration, find all time slots during which both people are available for at least the given duration. Each calendar entry is a pair of times in "HH:MM" format, and the daily bounds define the window outside of which a person is unavailable.

Intuition

The core idea is to merge both calendars into a single unified "busy" timeline, then look for gaps in that timeline that are long enough to fit the requested meeting. Before merging, we convert each person's unavailability outside their daily bounds into explicit busy blocks. Once all busy intervals are collected and sorted, we flatten overlapping intervals, and the free slots between consecutive merged intervals represent mutual availability.

Approach

  1. Normalize daily bounds: For each person, add a busy block from "00:00" to their start-of-day and from their end-of-day to "23:59". This ensures time outside working hours is treated as busy.
  2. Merge calendars: Combine both people's busy intervals into one list.
  3. Sort by start time: Sort the combined list of intervals by their start time.
  4. Flatten overlapping intervals: Iterate through sorted intervals, merging any that overlap or are adjacent into single blocks.
  5. Find gaps: Walk through the flattened intervals. The gap between the end of one interval and the start of the next is a free window. If that gap is greater than or equal to the required meeting duration, include it in the result.
  6. Convert back to "HH:MM" format if needed.

Pseudocode

function calendarMatching(cal1, bounds1, cal2, bounds2, duration):
    # Convert times to minutes for easier arithmetic
    updatedCal1 = [["00:00", bounds1[0]]] + cal1 + [[bounds1[1], "23:59"]]
    updatedCal2 = [["00:00", bounds2[0]]] + cal2 + [[bounds2[1], "23:59"]]

    merged = merge(updatedCal1, updatedCal2)  # combine and sort
    merged.sort(by start time)

    # Flatten overlapping intervals
    flattened = [merged[0]]
    for i from 1 to len(merged) - 1:
        if merged[i].start <= flattened[-1].end:
            flattened[-1].end = max(flattened[-1].end, merged[i].end)
        else:
            flattened.append(merged[i])

    # Extract available slots
    availableSlots = []
    for i from 1 to len(flattened) - 1:
        gapStart = flattened[i - 1].end
        gapEnd = flattened[i].start
        if gapEnd - gapStart >= duration:
            availableSlots.append([gapStart, gapEnd])

    return availableSlots

Time & Space Complexity

  • Time: O((c1 + c2) log(c1 + c2)) where c1 and c2 are the sizes of the two calendars. The dominant cost is sorting the merged interval list.
  • Space: O(c1 + c2) for the merged and flattened interval lists.

Key Insights

  • Converting "unavailable outside bounds" into explicit busy intervals greatly simplifies the logic; the entire problem becomes a standard interval-merge question.
  • Working in minutes (integer arithmetic) avoids string-parsing complexity during comparisons.
  • The flatten step is identical to the classic "merge overlapping intervals" problem.
  • Gaps between consecutive flattened intervals directly represent mutual free time.

Edge Cases

  • No overlapping working hours: the daily bounds of the two people do not intersect, so no meeting is possible.
  • One or both calendars are completely empty: the entire overlapping working-hours window is available.
  • The required duration is zero: every infinitesimal gap qualifies (typically constrained to be at least 1 minute in practice).
  • Meetings that are back-to-back with no gap: no free slot between them.
  • Identical calendars: the merged and flattened calendar is the same as either one, and gaps are found from it.
  • Daily bounds that start and end at the same time: no availability for that person.

Linked mentions