Compute max team size with a core interval
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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, labeled `1..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, m` efficiently (assume you may need near **O(log m)** or **O(m)** time, depending on constraints).
Quick Answer: 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.
Part 1: Maximum Team Size With a Core Employee
You are given two equal-length arrays startTime and endTime. Employee i works during the inclusive interval [startTime[i], endTime[i]].
A team is valid if you can choose one employee as the core employee and that core employee's interval intersects every other chosen team member's interval. Two intervals [a, b] and [c, d] intersect if max(a, c) <= min(b, d).
Return the maximum possible size of a valid team.
If there are no employees, return 0.
Constraints
- 0 <= n <= 2 * 10^5
- len(startTime) == len(endTime) == n
- 0 <= startTime[i] <= endTime[i] <= 10^9
- Your algorithm should be better than O(n^2)
Examples
Input: ([2, 5, 6, 8], [5, 6, 10, 9])
Expected Output:
Explanation: Choosing employee 2 with interval [5, 6] gives a team of size 3: [2,5], [5,6], and [6,10].
Input: ([1, 2, 3], [2, 3, 4])
Expected Output:
Explanation: The middle interval [2,3] intersects both neighbors because endpoint touching counts as overlap.
Input: ([1, 3, 5], [1, 3, 5])
Expected Output:
Explanation: All intervals are disjoint single points, so no employee overlaps any other.
Input: ([7], [7])
Expected Output:
Explanation: With one employee, that employee forms a valid team alone.
Input: ([], [])
Expected Output:
Explanation: There are no employees, so no team can be formed.
Solution
def solution(startTime, endTime):
from bisect import bisect_left, bisect_right
n = len(startTime)
if n == 0:
return 0
starts = sorted(startTime)
ends = sorted(endTime)
best = 0
for s, e in zip(startTime, endTime):
# Intervals with start <= e
started_in_time = bisect_right(starts, e)
# Intervals with end < s
ended_too_early = bisect_left(ends, s)
overlaps = started_in_time - ended_too_early
if overlaps > best:
best = overlaps
return bestExplanation
**Key reframing.** A non-core interval `[c, d]` intersects the core `[s, e]` exactly when `max(s, c) <= min(e, d)`, which simplifies to two independent conditions: `c <= e` (it starts no later than the core ends) **and** `d >= s` (it ends no earlier than the core starts). So for a fixed core, the answer is "how many intervals satisfy both `start <= e` and `end >= s`."
**Counting with sorted arrays + binary search.** Sort all start times into `starts` and all end times into `ends` once (O(n log n)). For each candidate core `[s, e]`:
- `bisect_right(starts, e)` → number of intervals with `start <= e`.
- `bisect_left(ends, s)` → number of intervals with `end < s` (i.e. those that fail the `end >= s` test).
The intervals that intersect the core are exactly `start <= e` minus those that also have `end < s`. This subtraction is valid because the two excluded groups (`start > e` and `end < s`) are disjoint — an interval can't have `start > e >= s > end` since `start <= end`. So `overlaps = bisect_right(starts, e) - bisect_left(ends, s)` is precise inclusion–exclusion.
**Why it's correct.** Every valid team is pinned by some core employee, and trying each employee as the core covers all teams; the maximum over cores is the answer. The core always counts itself (`start <= e` and `end >= s` both hold), so the result is `>= 1` whenever `n >= 1`. Empty input short-circuits to `0`.
This beats the required `O(n^2)` brute force: instead of comparing every pair, each core is answered in O(log n) via two binary searches.
Time complexity: O(n log n). Space complexity: O(n).
Hints
- For a fixed core interval [s, e], another interval overlaps it exactly when its start is <= e and its end is >= s.
- Sort all start times and all end times separately. Then use binary search to count how many intervals can overlap each employee's interval.
Part 2: Count Valid Process Allocations With No Equal Adjacent Slots
You must assign processes to time slots. There are n distinct processes labeled 1 through n, and you need an allocation sequence of length m.
A sequence is valid if no process appears in two consecutive time slots. In other words, for every t > 1, assignment[t] != assignment[t - 1].
Return the number of valid sequences modulo 1000000007.
If m = 0, the empty sequence counts as one valid allocation.
Constraints
- 0 <= n <= 10^9
- 0 <= m <= 10^18
- The answer must be returned modulo 10^9 + 7
- The solution should handle very large m efficiently
Examples
Input: (3, 2)
Expected Output:
Explanation: Choose any of 3 processes for the first slot, then 2 different processes for the second slot: 3 * 2 = 6.
Input: (2, 4)
Expected Output:
Explanation: Only two alternating sequences are possible: [1,2,1,2] and [2,1,2,1].
Input: (5, 1)
Expected Output:
Explanation: With one slot, any of the 5 processes can be chosen.
Input: (1, 3)
Expected Output:
Explanation: With only one process available, it is impossible to fill 3 slots without repeating consecutively.
Input: (4, 0)
Expected Output:
Explanation: There is exactly one empty allocation.
Solution
def solution(n, m):
MOD = 10**9 + 7
if m == 0:
return 1
if n == 0:
return 0
return (n % MOD) * pow((n - 1) % MOD, m - 1, MOD) % MODExplanation
This counts length-`m` sequences over `n` distinct processes where no two adjacent slots hold the same process — a standard **chromatic-style counting** argument.
**Counting by position.** Build the sequence left to right:
- The **first** slot can be any of the `n` processes.
- **Every later** slot can be anything *except* whatever sat in the immediately previous slot, giving `n - 1` choices each.
Multiplying the independent per-slot choices gives the closed form:
```
count = n * (n - 1)^(m - 1) for m >= 1
```
**Edge cases (handled explicitly):**
- `m == 0` → returns `1`: the empty sequence is the single valid allocation.
- `n == 0` with `m >= 1` → returns `0`: no process exists to fill a slot.
- `n == 1`, `m == 1` → `1 * pow(0, 0) = 1` (one slot, one way).
- `n == 1`, `m > 1` → `1 * pow(0, m-1) = 0`: the lone process would have to repeat.
**Why it stays fast.** Constraints allow `m` up to `10^18`, so the power can't be looped. The code uses Python's built-in `pow((n-1) % MOD, m - 1, MOD)`, which does **fast modular exponentiation** by squaring in `O(log m)` multiplications, each taken mod `10^9 + 7`. The bases are reduced mod `MOD` first (`n % MOD`, `(n-1) % MOD`) so the arithmetic stays within machine-friendly ranges before the final `% MOD`. The result is the formula above, evaluated entirely under the modulus.
Time complexity: O(log m). Space complexity: O(1).
Hints
- How many choices do you have for the first slot? How many choices remain for each later slot?
- Once you derive the formula, use fast modular exponentiation instead of multiplying in a loop.