Process Scheduling (No Consecutive)

Process Scheduling (No Consecutive) Problem Overview

The Citadel interview question "Process Scheduling (No Consecutive)" involves combinatorics to count valid ways to assign processes to time slots with restrictions. You have n distinct processes and m time intervals (often n processes and n intervals), scheduling one process per interval such that no process runs in consecutive intervals. Return the count modulo 10^9 + 7.[1]

Full Problem Statement

Given n processes labeled 1 to n and m time slots, compute the number of ways to assign processes to slots where:

• Exactly one process per slot.
• No process appears in two consecutive slots (adjacent slots must have different processes). This is a classic recurrence relation problem, solvable via dynamic programming, matching the tags.[1]

Input/Output Examples

No official test cases exist publicly, but examples from discussions illustrate:

• Input: n=2 processes, m=4 slots
  Valid schedules: ABAB, BABA (2 ways).
  Output: 2[1]

• Input: n=3 processes, m=4 slots
  Partial examples: ABCA, ABAB, ABAC, ABCB, ACAB, ACBA, ACAC, ACBC (more exist via permutation).
  Total exceeds naive counts due to non-consecutive constraint.[1]

Constraints

Exact constraints are unconfirmed but inferred from discussions:

• 1 ≤ n, m ≤ 10^5 (suggesting O(m) DP or matrix exponentiation for efficiency).
• Modulo 10^9 + 7 required, implying large results.
• n = m common in OA versions.[1]

Solution Approach

Define dp[i][j] as ways to fill first i slots, ending with process j.
Recurrence: dp[i][j] = sum(dp[i-1][k]) for all k ≠ j.
Optimized: Total for slot i is (n - 1) * (ways for slot i-1), with first slot having n choices.
Formula: n * (n-1)^{m-1} mod (10^9 + 7), computable via binary exponentiation.[1]