Quick Overview

This question evaluates proficiency with interval manipulation, timeline merging, and algorithmic reasoning for scheduling constraints, measuring competency in handling sorted interval lists, edge-case sanitization, and complexity analysis.

Find earliest common meeting slot

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given K participants' calendars, each a list of busy intervals [start, end) within a working window [workStart, workEnd], and a meeting duration d minutes, return the earliest interval [t, t + d) that is within every participant's working window and does not overlap any busy interval. Times are integers in minutes from 00:00. Busy intervals are non-overlapping and sorted within each calendar. If no slot exists, return an empty list. Design an algorithm, state its time and space complexity, and describe how you would handle unsorted or overlapping inputs and large K efficiently.

Quick Answer: This question evaluates proficiency with interval manipulation, timeline merging, and algorithmic reasoning for scheduling constraints, measuring competency in handling sorted interval lists, edge-case sanitization, and complexity analysis.

You are given K participants. calendars[i] is a list of busy half-open intervals [start, end) in minutes from 00:00, and work_windows[i] = [workStart, workEnd] represents that participant's available working window, interpreted as [workStart, workEnd). Given an integer d, return the earliest half-open interval [t, t + d) that lies inside every participant's working window and does not overlap any busy interval from any participant. Return the answer as [t, t + d]. If no such slot exists, return []. For the core problem, calendars are intended to be sorted and non-overlapping. As a follow-up, explain how you would normalize unsorted or overlapping calendars first, and how to stay efficient when K is large.

Constraints

  • 1 <= len(calendars) == len(work_windows) <= 100000
  • 0 <= total number of busy intervals across all calendars <= 200000
  • 0 <= start < end <= 1440
  • 0 <= workStart < workEnd <= 1440
  • 1 <= d <= 1440

Examples

Input: ([[[540, 570], [630, 660]], [[555, 585], [615, 645]], [[600, 615]]], [[480, 720], [540, 690], [510, 660]], 15)

Expected Output: [585, 600]

Explanation: The common working window is [540, 660). After merging busy times across all three calendars, the first free gap of length 15 is [585, 600).

Input: ([[[540, 600], [620, 660]], [[530, 610]], [[600, 650]]], [[540, 660], [540, 660], [540, 660]], 10)

Expected Output: []

Explanation: All busy intervals merge to cover the entire common working window [540, 660), so no 10-minute slot exists.

Hints

  1. Any valid meeting must lie inside the intersection of all participants' working windows.
  2. After clipping busy intervals to that common window, treat each calendar as a sorted stream and merge the K streams with a min-heap instead of flattening everything when K is large.

Loading coding console...