Compute max team size with a core interval
Quick Overview
This question evaluates algorithmic problem-solving around interval overlap and time-complexity optimization, measuring the ability to determine the maximum team size given a core interval while reasoning about interval intersections and scalability; it is commonly asked to assess correctness and subquadratic runtime thinking, categorized under Coding & Algorithms and emphasizing practical algorithmic implementation. The follow-up evaluates combinatorics and counting under adjacency constraints with modular arithmetic and efficient handling of large parameters, commonly posed to test recurrence reasoning and scalable counting approaches, falling under combinatorics/dynamic programming and emphasizing conceptual understanding linked to practical algorithmic efficiency.
You are given n employees’ working-time intervals, where employee i works during the inclusive interval [startTime[i], endTime[i]].
You want to form a team such that:
- The team contains at least one “core employee” .
-
The chosen core employee’s interval
intersects (overlaps) with every other team member’s interval
.
- Intervals [a,b] and [c,d] are considered intersecting if they share at least one time point, i.e., max(a,c) ≤ min(b,d) .
Return the maximum possible team size.
Example
-
Input:
-
startTime = [2, 5, 6, 8] -
endTime = [5, 6, 10, 9]
-
-
Output:
3
Requirements
- Your solution must be more efficient than O(n²) (assume time limits will fail quadratic solutions).
Follow-up (second question)
Grace Hopper’s scheduling rule: you must assign processes to time slots so that no process occupies two consecutive time slots.
Given:
-
n_processes = n(number of distinct processes, labeled1..n) -
n_intervals = m(number of time slots)
Count the number of valid allocations (sequences) of length m over n processes such that:
-
For all
t > 1,assignment[t] != assignment[t-1]
Return the count modulo (10^9 + 7).
Example
If n = 3, m = 2, valid sequences include (1,2), (1,3), (2,1), etc., but not (1,1).
Requirements
-
Handle large
n, mefficiently (assume you may need near O(log m) or O(m) time, depending on constraints).