Quick Overview

A scheduling coding problem: given everyone's busy intervals as text entries with inclusive minute times, find the earliest start for a meeting of k minutes after the day's first busy minute, or report that none exists. It tests time parsing, merging overlapping intervals and off-by-one boundaries.

Earliest K-Minute Meeting Start from Text Schedules with Inclusive Busy Times

Company: Visa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Everyone listed in a set of schedules must attend one meeting of `k` minutes. Each schedule entry is a string with four space-separated fields, a person's name, an activity, a start time and an end time, such as `"Sam sleep 02:00 10:00"`. Return the earliest time at which the meeting can start, as an `"HH:MM"` string, or `"-1"` if it cannot be held that day. ### Function Signature ```python def earliest_meeting(schedules: list[str], k: int) -> str: ``` ### Rules - Time is measured in whole minutes of one day, from `00:00` to `23:59`. An entry with start time `a` and end time `b` makes every minute from `a` through `b` busy, both ends included, so `"Lilly exercise 12:00 12:59"` covers exactly 60 minutes. - A minute is free if no entry covers it. Entries may overlap, whether they belong to the same person or to different people. Names and activities do not affect the answer. - A meeting that starts at minute `s` occupies minutes `s` through `s + k - 1`. All of them must be free, and the last one must not be later than `23:59`. - The meeting must start later than the first busy minute of the day: free time before the earliest busy interval does not count. This rule is why Example 1 returns `"10:01"` even though `00:00` through `01:59` is free. - Return the earliest valid start formatted as `"HH:MM"`, with a two-digit hour and a two-digit minute, or `"-1"` if no start is valid. ### Constraints - `1 <= len(schedules) <= 10^4` - Each entry has exactly four fields separated by single spaces. The name and the activity are nonempty strings of English letters. Both times are valid zero-padded `HH:MM` times from `00:00` to `23:59`, and the start time is not later than the end time. - `1 <= k <= 1440` ### Examples **Example 1** ```text Input: schedules = ["Sam sleep 02:00 10:00", "Lilly exercise 12:00 12:59"], k = 90 Output: "10:01" ``` The busy minutes are `02:00` through `10:00` and `12:00` through `12:59`. The free time before `02:00` does not count. From `10:01` through `11:59` there are 119 free minutes, enough for 90. **Example 2** ```text Input: schedules = ["Sam sleep 02:00 10:00", "Lilly exercise 12:00 12:59"], k = 180 Output: "13:00" ``` The 119 free minutes after `10:00` are too few. From `13:00` through `23:59` there are 660 free minutes. **Example 3** ```text Input: schedules = ["Ann work 08:00 11:00", "Bo gym 10:30 12:00", "Cy call 12:30 23:30"], k = 30 Output: "-1" ``` The first two entries overlap, so the busy time is `08:00` through `12:00` and `12:30` through `23:30`. The free stretches after the first busy minute, `12:01` through `12:29` and `23:31` through `23:59`, have 29 minutes each, one short of 30.

Overview: A scheduling coding problem: given everyone's busy intervals as text entries with inclusive minute times, find the earliest start for a meeting of k minutes after the day's first busy minute, or report that none exists. It tests time parsing, merging overlapping intervals and off-by-one boundaries.

Read the full Visa Software Engineer interview experience this question came from

Everyone listed in a set of schedules must attend one meeting that lasts `k` minutes. Each schedule entry is a string with four space-separated fields: a person's name, an activity, a start time and an end time, such as `"Sam sleep 02:00 10:00"`. Return the earliest time at which the meeting can start, as an `"HH:MM"` string, or `"-1"` if it cannot be held that day. ### Rules - Time is measured in whole minutes of one day, from `00:00` to `23:59`. An entry with start time `a` and end time `b` makes every minute from `a` through `b` busy, both ends included, so `"Lilly exercise 12:00 12:59"` covers exactly 60 minutes. - A minute is free if no entry covers it. Entries may overlap, whether they belong to the same person or to different people, and they may appear in any order. Names and activities do not affect the answer. - A meeting that starts at minute `s` occupies minutes `s` through `s + k - 1`. All of them must be free, and the last one must not be later than `23:59`. - The meeting must start later than the first busy minute of the day (the earliest start time among all entries): free time before the earliest busy interval does not count, however long it is. This rule is why Example 1 returns `"10:01"` even though `00:00` through `01:59` is free. - Return the earliest valid start formatted as `"HH:MM"`, with a two-digit zero-padded hour and a two-digit zero-padded minute, or `"-1"` if no start is valid. All values fit in 32-bit integers. ### Function Signature ```python def earliest_meeting(schedules: list[str], k: int) -> str: ``` ### Constraints - `1 <= len(schedules) <= 10^4` - Each entry has exactly four fields separated by single spaces. The name and the activity are nonempty strings of English letters (at most 20 letters each). Both times are valid zero-padded `HH:MM` times from `00:00` to `23:59`, and the start time is not later than the end time. - `1 <= k <= 1440` ### Examples **Example 1** ```text Input: schedules = ["Sam sleep 02:00 10:00", "Lilly exercise 12:00 12:59"], k = 90 Output: "10:01" ``` The busy minutes are `02:00` through `10:00` and `12:00` through `12:59`. The free time before `02:00` does not count. From `10:01` through `11:59` there are 119 free minutes, enough for 90. **Example 2** ```text Input: schedules = ["Sam sleep 02:00 10:00", "Lilly exercise 12:00 12:59"], k = 180 Output: "13:00" ``` The 119 free minutes after `10:00` are too few. From `13:00` through `23:59` there are 660 free minutes, so the meeting starts at `13:00`.

Constraints

  • 1 <= len(schedules) <= 10^4
  • Each entry has exactly four fields separated by single spaces: name, activity, start time, end time.
  • The name and the activity are nonempty strings of English letters (at most 20 letters each).
  • Both times are valid zero-padded HH:MM times from 00:00 to 23:59, and the start time is not later than the end time.
  • 1 <= k <= 1440

Examples

Input: (['Sam sleep 02:00 10:00', 'Lilly exercise 12:00 12:59'], 90)

Expected Output: '10:01'

Explanation: Example 1: busy 02:00-10:00 and 12:00-12:59; the free time before 02:00 is ignored, and 10:01-11:59 (119 free minutes) fits 90.

Input: (['Sam sleep 02:00 10:00', 'Lilly exercise 12:00 12:59'], 180)

Expected Output: '13:00'

Explanation: Example 2: the 119-minute gap after 10:00 is too short, so the later stretch 13:00-23:59 (660 minutes) is used.

Hints

  1. Turn every HH:MM time into a minute number from 0 to 1439, and remember that both the start minute and the end minute of an entry are busy.
  2. Only minutes after the earliest busy minute of the day can be used, and the meeting's last minute must be 23:59 or earlier.
  3. Entries can overlap, nest, repeat or touch: an entry ending at 10:00 followed by one starting at 10:01 leaves no free minute between them.

Loading coding console...

Show the approach

Approach

Convert each HH:MM time to a minute index t = 60 * HH + MM in 0..1439. Record coverage with a difference array of 1441 slots: an entry covering minutes a..b (both ends inclusive) adds 1 at a and subtracts 1 at b + 1, so the running prefix sum at minute m is the number of entries covering m, and m is free exactly when that sum is 0. Overlapping, nested, duplicate and unsorted entries therefore need no special handling, and names and activities are ignored. Let f be the smallest start time over all entries, the first busy minute of the day. Scan minutes 0..1439 in order and keep run, the length of the current block of consecutive free minutes, resetting it to 0 at every busy minute and at every minute m <= f. Invariant: after minute m, run is the number of consecutive free minutes ending at m that all lie after f. The first time run reaches k, at minute m, the minutes m - k + 1 .. m are all free, all after f, and end no later than 23:59, so s = m - k + 1 is a valid start. It is the earliest: any valid start s' < s would end at s' + k - 1 < m, and the run would already have reached k at that earlier minute. If the scan finishes without run reaching k, no valid start exists and the answer is "-1". The start is formatted with a zero-padded two-digit hour and minute. Edge cases: k = 1440 never fits because minute f itself is busy; if the busy block containing f extends to 23:59 there is no candidate; adjacent entries such as one ending 10:00 and one starting 10:01 leave no free minute between them; the free stretch after the last busy minute through 23:59 is a valid candidate; a meeting that would run past 23:59 is rejected because the scan stops at minute 1439.

Time complexity:
O(n + 1440)
Space complexity:
O(1440)