algorithms/leetcode/3680-GenerateSchedule.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main

// 3680. Generate Schedule
// You are given an integer n representing n teams.
// You are asked to generate a schedule such that:
//     1. Each team plays every other team exactly twice: once at home and once away.
//     2. There is exactly one match per day; the schedule is a list of consecutive days and schedule[i] is the match on day i.
//     3. 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.

// Example 1:
// Input: n = 3
// Output: []
// Explanation:
// Since each team plays every other team exactly twice, a total of 6 matches need to be played: [0,1],[0,2],[1,2],[1,0],[2,0],[2,1].
// It's not possible to create a schedule without at least one team playing consecutive days.

// Example 2:
// Input: n = 5
// Output: [[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]]
// Explanation:
// Since each team plays every other team exactly twice, a total of 20 matches need to be played.
// The output shows one of the schedules that meet the conditions. No team plays on consecutive days.

// Constraints:
//     2 <= n <= 50

import "fmt"
import "slices"

func generateSchedule(n int) [][]int {
    if n <= 4 { return [][]int{} }
    res := [][]int{{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}}
    if n == 5 { return res }
    addTeam := func(arr [][]int, n int) [][]int {
        adding := make([][]int, 0)
        for i := 0; i < n; i++ {
            adding = append(adding, []int{i, n}, []int{n, i})
        }
        for len(adding) > 0 {
            addingNow := adding[0]
            a1, a2 := addingNow[0], addingNow[1]
            for i := 0; i < len(arr)-1; i++ {
                if (arr)[i][0] != a1 && (arr)[i][0] != a2 && (arr)[i][1] != a1 && (arr)[i][1] != a2 &&
                    (arr)[i+1][0] != a1 && (arr)[i+1][0] != a2 && (arr)[i+1][1] != a1 && (arr)[i+1][1] != a2 {
                    arr = slices.Concat(arr[:i+1], [][]int{{a1, a2}}, arr[i+1:])
                    adding = adding[1:]
                    break
                }
            }
        }
        return arr
    }
    for i := 5; i <= n - 1; i++ {
        res = addTeam(res, i)
    }
    return res
}

func generateSchedule1(n int) [][]int {
    if n < 5 { return nil }
    res := make([][]int, 0, n*(n-1))
    for d := 2; d < n-1; d++ {
        for i := range n {
            res = append(res, []int{i, (i + d) % n })
        }
    }
    for i := 0; i < n; i++ {
        res = append(res, []int{i, (i+1) % n}, []int{(i+n-1) % n, (i+n-2) % n})
    }
    return res
}

func main() {
    // Example 1:
    // Input: n = 3
    // Output: []
    // Explanation:
    // Since each team plays every other team exactly twice, a total of 6 matches need to be played: [0,1],[0,2],[1,2],[1,0],[2,0],[2,1].
    // It's not possible to create a schedule without at least one team playing consecutive days.
    fmt.Println(generateSchedule(3)) // []
    // Example 2:
    // Input: n = 5
    // Output: [[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]]
    // Explanation:
    // Since each team plays every other team exactly twice, a total of 20 matches need to be played.
    // The output shows one of the schedules that meet the conditions. No team plays on consecutive days.
    fmt.Println(generateSchedule(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]]

    fmt.Println(generateSchedule(2)) // []
    fmt.Println(generateSchedule(50)) //

    fmt.Println(generateSchedule1(3)) // []
    fmt.Println(generateSchedule1(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]]
    fmt.Println(generateSchedule1(2)) // []
    fmt.Println(generateSchedule1(50)) //
}