LeetCode-Solutions/Python/generate-schedule.py at master · kamyu104/LeetCode-Solutions · 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
# Time:  O(n^2)
# Space: O(1)

# constructive algorithms
class Solution(object):
    def generateSchedule(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        result = []
        if n <= 4:
            return result
        l = 1
        if n%2 == 0:
            for i in xrange(0, n, 2):
                result.append([i, i+l])
            for i in xrange(0, n, 2):
                result.append([i+l, i])
            for i in xrange(1, n, 2):
                result.append([i, (i+l)%n])
            for i in xrange(1, n, 2):
                result.append([(i+l)%n, i])
        else:
            for i in xrange(0, 2*n, 2):
                result.append([i%n, (i+l)%n])
            for i in xrange(0, 2*n, 2):
                result.append([(i+l)%n, i%n])
        for l in xrange(2, (n+1)//2):
            j = result[-1][0]+1
            for i in xrange(j, j+n):
                result.append([i%n, (i+l)%n])
            j = result[-1][1]-1
            for i in xrange(j, j+n):
                result.append([(i+l)%n, i%n])
        if n%2 == 0:
            l = n//2
            j = result[-1][0]-1
            for i in xrange(j, j+n):
                result.append([i%n, (i+l)%n])
        return result