Katkat
Back

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

VisaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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

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

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

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

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.