2026-02-10：生成赛程。用go语言，给定一个正整数 n，表示共有 n 支队伍。你的任务是安排一连串的比赛日程，要求如下：

• 每对队伍要互相对战两次，且一场做主队一场做客队；

• 每一天只进行一场比赛，日程由连续的天数组成，schedule[i] 表示第 i 天的那场比赛；

• 任何一支队伍不能在相邻的两个比赛日都有比赛（即不能连续两天出场）；

• 输出一个二维整数数组 schedule，schedule[i][0] 表示第 i 天的主队编号，schedule[i][1] 表示客队编号；

• 若存在多种满足条件的安排，返回任意一种；如果无法满足上述约束，则返回空数组。

（注：总共需要安排的比赛场数为 n(n-1)，因为每一对队伍要进行两场比赛。）

2 <= n <= 50。

输入： 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 场比赛。

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

题目来自力扣3680。

🧠 程序工作流程详解

1. 输入验证与初始化

   • 程序首先检查输入的队伍数量n是否小于5。如果n < 5，则直接返回nil（空数组）。这是因为对于较小的n（如2, 3, 4），可能无法满足“任何队伍不能连续两天出场”的约束，或者需要特殊处理，代码选择了一种简单的处理方式。
   • 接着，程序初始化所有需要进行的比赛。对于n支队伍，每对队伍要互相对战两次（一次主客场互换），因此总比赛场数为 n * (n - 1)。程序通过两层循环遍历所有队伍编号的组合（i和j，且j != i），将每一对[i, j]（表示队伍i主场对阵队伍j）加入到初始比赛列表perm中。

2. 随机搜索有效赛程

   • 程序进入一个无限循环，目标是找到一种比赛的排列顺序，能够满足所有约束条件。
   • 在每次循环中，程序首先使用rand.Shuffle函数将初始比赛列表perm随机打乱顺序。随机化是避免陷入无效排列的关键策略，增加了找到解的可能性。
   • 然后，程序调用gen函数，并传入打乱后列表的一个副本（使用slices.Clone创建，以避免修改原始的打乱列表），尝试构建一个有效的赛程。

3. 构建有效赛程序列 (gen函数)

   • gen函数的核心任务是按顺序处理输入的比赛列表，检查并构建一个满足“无队伍连续出场”约束的赛程序列。
   • 启动序列：它将随机排列的第一个比赛直接加入到结果序列ans中，并从待处理列表perm中移除该比赛。
   • 贪心选择后续比赛：函数进入一个循环，只要待处理列表perm不为空，就继续寻找下一场比赛。
     • 它从后向前遍历当前待处理列表perm（使用slices.Backward）。这样设计是为了在删除元素时（因为Go中切片删除元素需要移动后面的数据），移动的数据量更少，效率稍高。
     • 对于遍历到的每一场比赛p，函数检查其是否与结果序列中的最后一场比赛last冲突。冲突的条件是：比赛p中的任一支队伍（无论是主队还是客队）出现在比赛last中。也就是说，需要确保p[0]和p[1]都不等于last[0]和last[1]。
     • 添加无冲突比赛：如果比赛p与最后一场比赛无冲突，它就被加入到结果序列ans的末尾，并从待处理列表perm中移除。然后，循环立即跳出，继续寻找下一场比赛（continue next）。
   • 处理失败情况：如果遍历完整个待处理列表perm，都找不到一场与当前最后比赛无冲突的比赛，说明当前随机打乱的序列无法成功构建有效赛程。gen函数返回nil，表示此次尝试失败。
   • 外部循环（在generateSchedule中）一旦接收到gen函数返回的非nil结果（即一个构建成功的完整赛程），就立即返回该结果。如果gen返回nil，外部循环会进行下一次随机打乱并重试。

⏱️ 复杂度分析

• 时间复杂度：

  • 最坏情况下，程序可能需要尝试非常多次（与随机排列的数量相关）才能找到一个解，甚至可能找不到解（尽管对于n>=5，通常存在解）。每次尝试的主要成本在于gen函数，它需要检查所有n(n-1)场比赛的排列可能性。因此，最坏情况下的时间复杂度是超多项式的，可能接近 O((n(n-1))!)，这在n较大时是不可行的。但平均情况下，由于随机化，可能能在可接受的时间内找到解。
  • gen函数本身的时间复杂度为O((n(n-1))²)。因为外层循环最多执行n(n-1)次（每次添加一场比赛），内层循环在最坏情况下也需要遍历近乎整个剩余的未安排比赛列表（长度也是O(n(n-1))）。

• 额外空间复杂度：

  • 程序需要存储所有比赛的列表，其空间为O(n²)。在gen函数中，创建了输入列表的副本，并构建了同样大小的结果列表。此外，随机打乱是原地进行的。因此，总的额外空间复杂度主要取决于存储比赛列表所需的空间，为 O(n²)。

💎 核心机制总结

该程序通过随机生成比赛排列，并采用贪心算法逐个检查并添加满足约束的比赛来构建赛程。这是一种随机重启贪心搜索的策略。其成功高度依赖于随机打乱后序列的初始顺序，对于较大的n，可能需要较长的运行时间。

Go完整代码如下：

package main

import (
	"fmt"
	"math/rand/v2"
	"slices"
)

func gen(perm [][]int) (ans [][]int) {
	ans = append(ans, perm[0])
	perm = perm[1:]
next:
	for len(perm) > 0 {
		// 倒着遍历，这样删除的时候 i 更大，移动的数据少
		for i, p := range slices.Backward(perm) {
			last := ans[len(ans)-1]
			if p[0] != last[0] && p[0] != last[1] && p[1] != last[0] && p[1] != last[1] {
				// p 和上一场比赛无冲突
				ans = append(ans, p)
				perm = append(perm[:i], perm[i+1:]...) // 删除 perm[i]
				continue next                          // 找下一场比赛
			}
		}
		return nil
	}
	return
}

func generateSchedule(n int) [][]int {
	if n < 5 {
		return nil
	}

	// 初始化赛程排列
	perm := make([][]int, 0, n*(n-1))
	for i := range n {
		for j := range n {
			if j != i {
				perm = append(perm, []int{i, j})
			}
		}
	}

	for {
		rand.Shuffle(len(perm), func(i, j int) { perm[i], perm[j] = perm[j], perm[i] })
		if ans := gen(slices.Clone(perm)); ans != nil {
			return ans
		}
	}
}
func main() {
	n := 5
	result := generateSchedule(n)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import random
from typing import List, Optional

def gen(perm: List[List[int]]) -> Optional[List[List[int]]]:
    ans = [perm[0]]
    perm = perm[1:]
    
    while perm:
        found = False
        # 倒着遍历
        for i in range(len(perm) - 1, -1, -1):
            p = perm[i]
            last = ans[-1]
            if (p[0] != last[0] and p[0] != last[1] and 
                p[1] != last[0] and p[1] != last[1]):
                # p 和上一场比赛无冲突
                ans.append(p)
                perm.pop(i)  # 删除 perm[i]
                found = True
                break
        
        if not found:
            return None
    
    return ans

def generate_schedule(n: int) -> Optional[List[List[int]]]:
    if n < 5:
        return None
    
    # 初始化赛程排列
    perm = []
    for i in range(n):
        for j in range(n):
            if j != i:
                perm.append([i, j])
    
    while True:
        random.shuffle(perm)
        perm_copy = perm.copy()
        result = gen(perm_copy)
        if result is not None:
            return result

def main():
    n = 5
    result = generate_schedule(n)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

// 生成倒序遍历的索引序列
vector<int> backward_indices(int size) {
    vector<int> indices(size);
    for (int i = 0; i < size; i++) {
        indices[i] = size - 1 - i;
    }
    return indices;
}

vector<vector<int>> gen(vector<vector<int>> perm) {
    if (perm.empty()) return {};

    vector<vector<int>> ans;
    ans.push_back(perm[0]);
    perm.erase(perm.begin()); // 删除第一个元素

    while (!perm.empty()) {
        bool found = false;
        // 获取倒序遍历的索引
        vector<int> indices = backward_indices(perm.size());

        for (int i : indices) {
            const vector<int>& p = perm[i];
            const vector<int>& last = ans.back();

            if (p[0] != last[0] && p[0] != last[1] &&
                p[1] != last[0] && p[1] != last[1]) {
                // p 和上一场比赛无冲突
                ans.push_back(p);
                perm.erase(perm.begin() + i); // 删除 perm[i]
                found = true;
                break;
            }
        }

        if (!found) {
            return {};
        }
    }

    return ans;
}

vector<vector<int>> generateSchedule(int n) {
    if (n < 5) {
        return {};
    }

    // 初始化赛程排列
    vector<vector<int>> perm;
    perm.reserve(n * (n - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j != i) {
                perm.push_back({i, j});
            }
        }
    }

    // 使用随机数引擎
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937 rng(seed);

    while (true) {
        // 随机打乱
        shuffle(perm.begin(), perm.end(), rng);

        // 复制一份进行尝试
        vector<vector<int>> perm_copy = perm;
        vector<vector<int>> result = gen(perm_copy);

        if (!result.empty()) {
            return result;
        }
    }
}

int main() {
    int n = 5;
    vector<vector<int>> result = generateSchedule(n);

    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << "[" << result[i][0] << ", " << result[i][1] << "]";
        if (i < result.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return 0;
}