Employee free time · DSA Mastery

Scenario

The calendar app of a company lets a team find a meeting time. Every teammate has busy slots, and the app puts all of them into one list. A slot [start, end) is busy from the start minute up to, but not including, the end minute.

The team can only meet inside working hours, from minute open up to minute close. A meeting needs at least need minutes in a row when nobody is busy. Find every such stretch.

Your task

Write team_free_slots(busy, open, close, need).

busy[i] = [start, end), with start < end. Slots come from different people, in no order, and may overlap or lie partly outside working hours.
Two busy slots that touch, where one ends at the minute the next begins, leave no free minute between them.
Return the free stretches [a, b) inside [open, close), sorted by start, where nobody is busy and b - a >= need.

Examples

Example 1 (traced)#

text2 lines

Input:  busy = [[9, 12], [10, 11], [13, 15], [0, 2], [14, 16]], open = 8, close = 20, need = 1
Output: [[8, 9], [12, 13], [16, 20]]

Sort by start. Keep a cursor, the first minute not yet known to be busy, starting at open. A busy slot that starts after the cursor leaves a free stretch before it.

Next busy slot	Cursor before	Free stretch	Cursor after
[0, 2]	8	none: it starts before the cursor	8
[9, 12]	8	[8, 9)	12
[10, 11]	12	none	12
[13, 15]	12	[12, 13)	15
[14, 16]	15	none	16
end of the list	16	[16, 20)

Example 2#

text2 lines

Input:  busy = [[0, 30]], open = 5, close = 10, need = 1
Output: []

One slot covers all of working hours.

Example 3#

text2 lines

Input:  busy = [[0, 2], [4, 10]], open = 0, close = 10, need = 2
Output: [[2, 4]]

The stretch from 2 to 4 is exactly 2 minutes long, and that meets the need.

Constraints

0 ≤ busy.length ≤ 100,000
0 ≤ start < end ≤ 1,000,000,000 (minutes)
0 ≤ open < close ≤ 1,000,000,000, and 1 ≤ need ≤ 1,000,000,000

What does n ≤ 10^5 tell you?

Marking every minute is impossible when minutes go up to 10^9. Joining overlapping slots again and again costs about n × n. Sorting by start costs n log n, and one pass costs n.

Scenario

The team can only meet inside working hours, from minute open up to minute close. A meeting needs at least need minutes in a row when nobody is busy. Find every such stretch.

Your task

Write team_free_slots(busy, open, close, need).

busy[i] = [start, end), with start < end. Slots come from different people, in no order, and may overlap or lie partly outside working hours.
Two busy slots that touch, where one ends at the minute the next begins, leave no free minute between them.
Return the free stretches [a, b) inside [open, close), sorted by start, where nobody is busy and b - a >= need.

Examples

Example 1 (traced)#

text2 lines

Input:  busy = [[9, 12], [10, 11], [13, 15], [0, 2], [14, 16]], open = 8, close = 20, need = 1
Output: [[8, 9], [12, 13], [16, 20]]

Sort by start. Keep a cursor, the first minute not yet known to be busy, starting at open. A busy slot that starts after the cursor leaves a free stretch before it.

Next busy slot	Cursor before	Free stretch	Cursor after
[0, 2]	8	none: it starts before the cursor	8
[9, 12]	8	[8, 9)	12
[10, 11]	12	none	12
[13, 15]	12	[12, 13)	15
[14, 16]	15	none	16
end of the list	16	[16, 20)

Example 2#

text2 lines

Input:  busy = [[0, 30]], open = 5, close = 10, need = 1
Output: []

One slot covers all of working hours.

Example 3#

text2 lines

Input:  busy = [[0, 2], [4, 10]], open = 0, close = 10, need = 2
Output: [[2, 4]]

The stretch from 2 to 4 is exactly 2 minutes long, and that meets the need.

Constraints

0 ≤ busy.length ≤ 100,000
0 ≤ start < end ≤ 1,000,000,000 (minutes)
0 ≤ open < close ≤ 1,000,000,000, and 1 ≤ need ≤ 1,000,000,000

What does n ≤ 10^5 tell you?

Marking every minute is impossible when minutes go up to 10^9. Joining overlapping slots again and again costs about n × n. Sorting by start costs n log n, and one pass costs n.