Intervals with Exactly X Concurrent Meetings

Quick Overview

Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Intervals with Exactly X Concurrent Meetings

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Intervals with Exactly X Concurrent Meetings Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. A meeting ending at time t is not active at t, while a meeting starting at t is active. Return intervals sorted by start time and merge adjacent output intervals when the active count remains X across their boundary. If there are no meetings, return an empty list for every X. ## Function Contract Implement `intervals_with_concurrency(starts, ends, x) -> list[list[int]]`. ## Constraints - 0 <= number of meetings <= 200000. - 0 <= start < end <= 10^9 for every meeting. - 0 <= x <= number of meetings. - Zero-length output intervals must not be returned. - Spans before the minimum start and at or after the maximum end are outside the observation domain. ## Examples ```text starts = [1, 2, 4], ends = [5, 6, 7], x = 2 output = [[2, 4], [5, 6]] ``` ```text starts = [1, 5], ends = [2, 7], x = 0 output = [[2, 5]] ``` ```hint Test a shared boundary Include one meeting ending exactly when another starts and verify the half-open convention at that timestamp. ``` ```hint Exercise zero concurrency Use two separated meetings and check that only the finite gap inside the observation domain is returned when X is zero. ```

Quick Answer: Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

|Home/Coding & Algorithms/Google
Google logo
Google
Aug 1, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Intervals with Exactly X Concurrent Meetings

Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. A meeting ending at time t is not active at t, while a meeting starting at t is active. Return intervals sorted by start time and merge adjacent output intervals when the active count remains X across their boundary. If there are no meetings, return an empty list for every X.

Function Contract

Implement intervals_with_concurrency(starts, ends, x) -> list[list[int]].

Constraints

  • 0 <= number of meetings <= 200000.
  • 0 <= start < end <= 10^9 for every meeting.
  • 0 <= x <= number of meetings.
  • Zero-length output intervals must not be returned.
  • Spans before the minimum start and at or after the maximum end are outside the observation domain.

Examples

starts = [1, 2, 4], ends = [5, 6, 7], x = 2
output = [[2, 4], [5, 6]]
starts = [1, 5], ends = [2, 7], x = 0
output = [[2, 5]]

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...