Compute max team size with a core interval

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).

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

Example 1

Input: ([2, 5, 6, 8], [5, 6, 10, 9])
Output: 3

Explanation: Choosing employee 2 with interval [5, 6] gives a team of size 3: [2,5], [5,6], and [6,10].

Example 2

Input: ([1, 2, 3], [2, 3, 4])
Output: 3

Explanation: The middle interval [2,3] intersects both neighbors because endpoint touching counts as overlap.

Hints

1. For a fixed core interval [s, e], another interval overlaps it exactly when its start is <= e and its end is >= s.
2. Sort all start times and all end times separately. Then use binary search to count how many intervals can overlap each employee's interval.

Approach

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)

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

Example 1

Input: (3, 2)
Output: 6

Explanation: Choose any of 3 processes for the first slot, then 2 different processes for the second slot: 3 * 2 = 6.

Example 2

Input: (2, 4)
Output: 2

Explanation: Only two alternating sequences are possible: [1,2,1,2] and [2,1,2,1].

Hints

1. How many choices do you have for the first slot? How many choices remain for each later slot?
2. Once you derive the formula, use fast modular exponentiation instead of multiplying in a loop.

Approach

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:

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)