Earliest Meeting Time for All Employees
Problem statement
A day is measured in minutes, from minute 0 to minute 1440. You want to book one meeting of duration minutes that every employee can attend.
You are given schedules, where schedules[i] is the list of busy intervals of employee i. An interval [start, end] means the employee is busy from minute start up to, but not including, minute end. One employee's intervals can come in any order, and they can overlap or touch. An employee with an empty list is free all day.
A meeting that starts at minute t uses the time from t up to, but not including, t + duration. It is allowed when it fits inside the day (t >= 0 and t + duration <= 1440) and it does not overlap any busy interval of any employee. So a meeting may start at the exact minute a busy interval ends, and it may end at the exact minute a busy interval starts.
Return the earliest minute t at which an allowed meeting can start. If no allowed meeting exists, return -1.
Function
earliestMeetingTime(schedules: int[][][], duration: int) → intExamples
Example 1
schedules = [[[60,120],[300,360]],[[0,30],[150,200]],[[100,180]]]duration = 45return = 200Put every busy interval together: [0, 30), [60, 120), [100, 180), [150, 200) and [300, 360). The three in the middle overlap, so together they cover [60, 200). Someone is busy during [0, 30), [60, 200) and [300, 360).
The first time when everyone is free is [30, 60), but it is only 30 minutes long, which is less than 45. The next one is [200, 300), which is 100 minutes long, so the meeting can start at minute 200.
Example 2
schedules = [[[540,600],[0,540]],[[600,660]]]duration = 780return = 660The first employee's list is not sorted. The busy intervals [0, 540), [540, 600) and [600, 660) touch end to start, so someone is busy from minute 0 until minute 660.
An interval does not include its end minute, so the meeting can start at minute 660. It covers [660, 1440), which is exactly 780 minutes and ends right at the end of the day.
Example 3
schedules = [[],[[0,700]],[[720,1440]]]duration = 30return = -1The first employee has no busy intervals. The only time when nobody is busy is [700, 720), which is 20 minutes long. A 30-minute meeting does not fit anywhere, so the answer is -1.
Constraints
1 <= schedules.length <= 1000 <= schedules[i].length <= 20schedules[i][j].length == 20 <= schedules[i][j][0] < schedules[i][j][1] <= 14401 <= duration <= 1440