Medium

题目描述

给你一个整数 n 表示 n 支队伍。要求你生成一个赛程表，满足以下条件：

  • 每支队伍与其他每支队伍都要比赛两次：一次主场，一次客场。
  • 每天恰好有一场比赛；赛程表是连续天数的列表，schedule[i] 是第 i 天的比赛。
  • 没有队伍在连续的两天比赛。

返回一个二维整数数组 schedule，其中 schedule[i][0] 表示主队，schedule[i][1] 表示客队。如果有多个满足条件的赛程表，返回其中任意一个。

如果不存在满足条件的赛程表，返回空数组。

示例 1：

输入：n = 3

输出：[]

解释：

由于每支队伍与其他每支队伍都要比赛两次，总共需要进行 6 场比赛：[0,1],[0,2],[1,2],[1,0],[2,0],[2,1]。

不可能创建一个赛程表而不让至少一支队伍在连续的两天比赛。

示例 2：

输入：n = 5

输出：[[0,1],[2,3],[0,4],[1,2],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[2,0],[3,1],[4,0],[2,1],[4,3],[1,0],[3,2],[4,1],[3,0],[4,2]]

解释：

由于每支队伍与其他每支队伍都要比赛两次，总共需要进行 20 场比赛。

输出显示了满足条件的赛程表之一。没有队伍在连续的两天比赛。

约束条件：

  • 2 <= n <= 50

解题思路

这道题需要为 n 支队伍安排赛程，确保每支队伍都与其他队伍比赛两次（主客场各一次），且没有队伍连续两天比赛。

关键分析：

  • 总比赛场次为 n*(n-1) 场
  • 每天最多安排 n/2 场比赛（每支队伍最多参与一场）
  • 当 n 为奇数时，每天只能安排 (n-1)/2 场比赛，因为必有一支队伍轮空

解题思路：

  1. 可行性判断：当 n 为奇数且 n ≤ 3 时无解，因为比赛天数过少，无法满足不连续比赛的约束
  2. 贪心策略：优先选择剩余比赛场次最多的队伍进行配对，同时确保这些队伍在前一天没有比赛
  3. 状态维护：
    • 追踪每对队伍之间的剩余比赛次数
    • 记录每支队伍的总剩余比赛次数
    • 记录上一天参与比赛的队伍

算法流程： 每一天贪心地选择可用队伍中剩余比赛最多的一对进行配对，直到所有比赛安排完毕。如果某天无法找到合适的配对（避免连续比赛），则无解。

这种贪心策略能够有效平衡各队伍的比赛分布，避免某些队伍过早完成所有比赛而导致后续无法配对的情况。

代码实现

class Solution {
public:
    vector<vector<int>> generateSchedule(int n) {
        if (n % 2 == 1 && n <= 3) return {};
        
        // remaining[i][j] = number of remaining games between team i and j
        vector<vector<int>> remaining(n, vector<int>(n, 2));
        for (int i = 0; i < n; i++) {
            remaining[i][i] = 0;
        }
        
        // total remaining games for each team
        vector<int> totalRemaining(n, 2 * (n - 1));
        
        vector<vector<int>> schedule;
        vector<bool> playedYesterday(n, false);
        
        int totalGames = n * (n - 1);
        
        while (schedule.size() < totalGames) {
            vector<pair<int, int>> todaysMatches;
            vector<bool> playedToday(n, false);
            
            // Find the best match for today
            pair<int, int> bestMatch = {-1, -1};
            int maxSum = -1;
            
            for (int i = 0; i < n; i++) {
                if (playedYesterday[i] || playedToday[i]) continue;
                for (int j = i + 1; j < n; j++) {
                    if (playedYesterday[j] || playedToday[j]) continue;
                    if (remaining[i][j] > 0) {
                        int sum = totalRemaining[i] + totalRemaining[j];
                        if (sum > maxSum) {
                            maxSum = sum;
                            bestMatch = {i, j};
                        }
                    }
                }
            }
            
            if (bestMatch.first == -1) {
                return {}; // No valid schedule
            }
            
            int home = bestMatch.first;
            int away = bestMatch.second;
            
            // Decide who plays at home (alternate or prefer the one with more remaining games)
            if (totalRemaining[away] > totalRemaining[home]) {
                swap(home, away);
            }
            
            schedule.push_back({home, away});
            remaining[home][away]--;
            totalRemaining[home]--;
            totalRemaining[away]--;
            playedToday[home] = true;
            playedToday[away] = true;
            
            // Update played yesterday
            playedYesterday = playedToday;
        }
        
        return schedule;
    }
};

class Solution:
    def generateSchedule(self, n: int) -> List[List[int]]:
        if n % 2 == 1 and n <= 3:
            return []
        
        # remaining[i][j] = number of remaining games between team i and j
        remaining = [[2 if i != j else 0 for j in range(n)] for i in range(n)]
        
        # total remaining games for each team
        total_remaining = [2 * (n - 1) for _ in range(n)]
        
        schedule = []
        played_yesterday = [False] * n
        
        total_games = n * (n - 1)
        
        while len(schedule) < total_games:
            played_today = [False] * n
            
            # Find the best match for today
            best_match = (-1, -1)
            max_sum = -1
            
            for i in range(n):
                if played_yesterday[i] or played_today[i]:
                    continue
                for j in range(i + 1, n):
                    if played_yesterday[j] or played_today[j]:
                        continue
                    if remaining[i][j] > 0:
                        sum_remaining = total_remaining[i] + total_remaining[j]
                        if sum_remaining > max_sum:
                            max_sum = sum_remaining
                            best_match = (i, j)
            
            if best_match[0] == -1:
                return []  # No valid schedule
            
            home, away = best_match
            
            # Decide who plays at home (prefer the one with more remaining games)
            if total_remaining[away] > total_remaining[home]:
                home, away = away, home
            
            schedule.append([home, away])
            remaining[home][away] -= 1
            total_remaining[home] -= 1
            total_remaining[away] -= 1
            played_today[home] = True
            played_today[away] = True
            
            # Update played yesterday
            played_yesterday = played_today[:]
        
        return schedule

public class Solution {
    public int[][] GenerateSchedule(int n) {
        if (n % 2 == 1 && n <= 3) return new int[0][];
        
        // remaining[i][j] = number of remaining games between team i and j
        int[,] remaining = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                remaining[i, j] = i == j ? 0 : 2;
            }
        }
        
        // total remaining games for each team
        int[] totalRemaining = new int[n];
        for (int i = 0; i < n; i++) {
            totalRemaining[i] = 2 * (n - 1);
        }
        
        List<int[]> schedule = new List<int[]>();
        bool[] playedYesterday = new bool[n];
        
        int totalGames = n * (n - 1);
        
        while (schedule.Count < totalGames) {
            bool[] playedToday = new bool[n];
            
            // Find the best match for today
            int bestHome = -1, bestAway = -1;
            int maxSum = -1;
            
            for (int i = 0; i < n; i++) {
                if (playedYesterday[i] || playedToday[i]) continue;
                for (int j = i + 1; j < n; j++) {
                    if (playedYesterday[j] || playedToday[j]) continue;
                    if (remaining[i, j] > 0) {
                        int sum = totalRemaining[i] + totalRemaining[j];
                        if (sum > maxSum) {
                            maxSum = sum;
                            bestHome = i;
                            bestAway = j;
                        }
                    }
                }
            }
            
            if (bestHome == -1) {
                return new int[0][]; // No valid schedule
            }
            
            // Decide who plays at home (prefer the one with more remaining games)
            if (totalRemaining[bestAway] > totalRemaining[bestHome]) {
                int temp = bestHome;
                bestHome = bestAway;
                bestAway = temp;
            }
            
            schedule.Add(new int[] { bestHome, bestAway });
            remaining[bestHome, bestAway]--;
            totalRemaining[bestHome]--;
            totalRemaining[bestAway]--;
            playedToday[bestHome] = true;
            playedToday[bestAway] = true;
            
            // Update played yesterday
            playedYesterday = (bool[])playedToday.Clone();
        }
        
        return schedule.ToArray();
    }
}

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateSchedule = function(n) {
    if (n % 2 === 1) return [];
    
    const schedule = [];
    const totalRounds = 2 * (n - 1);
    
    for (let round = 0; round < totalRounds; round++) {
        const matches = [];
        
        for (let i = 0; i < n / 2; i++) {
            let home, away;
            
            if (i === 0) {
                home = 0;
                away = round % (n - 1) + 1;
            } else {
                const pos1 = (round - i) % (n - 1);
                const pos2 = (round + i) % (n - 1);
                home = pos1 === 0 ? n - 1 : pos1;
                away = pos2 === 0 ? n - 1 : pos2;
            }
            
            if (round >= n - 1) {
                [home, away] = [away, home];
            }
            
            matches.push([home, away]);
        }
        
        schedule.push(...matches);
    }
    
    return schedule;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n⁴)
空间复杂度O(n²)

说明：

  • 时间复杂度：需要安排 n(n-1) 场比赛，每场比赛需要遍历 O(n²) 对队伍找到最佳配对，总体为 O(n⁴)
  • 空间复杂度：需要 O(n²) 的二维数组存储队伍间的剩余比赛次数，以及 O(n) 的辅助数组

相关题目