Generate schedule

Array Math Greedy

23.9% acceptance

Feb 25, 2026

You are given an integer n representing n teams. You are asked to generate a schedule such that: Each team plays every other team exactly twice: once at home and once away. There is exactly one match per day; the schedule is a list of consecutive days and schedule[i] is the match on day i. No team plays on consecutive days. Return a 2D integer array schedule, where schedule[i][0] represents the home team and schedule[i][1] represents the away team. If multiple schedules meet the conditions, return any one of them. If no schedule exists that meets the conditions, return an empty array.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn generate_schedule(n: i32) -> Vec<Vec<i32>> {
    // n*(n-1) total directed matches (home + away for every pair).
    // Constraint: no team plays on consecutive days.
    //
    // Impossible cases (proved by pigeonhole / density arguments):
    //   n=2: only 2 matches sharing both teams -> impossible.
    //   n=3: 6 matches, each team plays 4 times, but ⌈6/2⌉=3 < 4 -> impossible.
    //   n=4: 12 matches, each team needs exactly 6 non-consecutive days out of 12
    //         (every other day). With 4 teams forced into two groups (odd/even days),
    //         pigeonhole requires ≥2 teams share a group but they can only fill 2
    //         directed matches against each other vs. 6 slots needed -> impossible.
    //   n≥5: feasible; the density 2*(n-1) / ⌈n*(n-1)/2⌉ ≤ 2/5 < 1, so room exists.
    //
    // Algorithm: Warnsdorff's heuristic (O(total^2) overall).
    //   - Precompute compatible[i] = list of matches that can follow match i.
    //   - Maintain degree[i] = count of unused compatible matches for match i.
    //   - At each step pick the unused compatible match with the smallest degree
    //     (fewest forward options -- avoids dead ends, same principle as knight's tour).
    //   - When a match is used, decrement degrees of its compatible neighbours.
    //   - Try every possible starting match; return on first complete schedule.
    let n = n as usize;
    if n <= 4 {
      return vec![];
    }

    let matches: Vec<(usize, usize)> = (0..n)
      .flat_map(|i| (0..n).filter(move |&j| j != i).map(move |j| (i, j)))
      .collect();
    let total = matches.len();

    // Precompute adjacency: two directed matches are compatible when they share no team.
    let compatible: Vec<Vec<usize>> = (0..total)
      .map(|i| {
        let (a, b) = matches[i];
        (0..total)
          .filter(|&j| {
            let (c, d) = matches[j];
            j != i && c != a && c != b && d != a && d != b
          })
          .collect()
      })
      .collect();

    let base_degree: Vec<usize> = (0..total).map(|i| compatible[i].len()).collect();

    // Try each starting match (Warnsdorff usually succeeds on the first few starts).
    for start in 0..total {
      let mut used = vec![false; total];
      let mut degree = base_degree.clone();
      let mut schedule: Vec<usize> = Vec::with_capacity(total);

      // Mark start as used and update neighbours' degrees.
      used[start] = true;
      schedule.push(start);
      for &j in &compatible[start] {
        degree[j] = degree[j].saturating_sub(1);
      }

      let mut last = start;
      let mut stuck = false;

      for _ in 1..total {
        // Pick unused compatible match with minimum degree (Warnsdorff's rule).
        let mut best = usize::MAX;
        let mut best_deg = usize::MAX;
        for &next in &compatible[last] {
          if used[next] { continue; }
          if degree[next] < best_deg {
            best_deg = degree[next];
            best = next;
          }
        }
        if best == usize::MAX {
          stuck = true;
          break;
        }
        used[best] = true;
        schedule.push(best);
        for &j in &compatible[best] {
          degree[j] = degree[j].saturating_sub(1);
        }
        last = best;
      }

      if !stuck {
        return schedule
          .iter()
          .map(|&i| vec![matches[i].0 as i32, matches[i].1 as i32])
          .collect();
      }
    }

    vec![]
  }
}