Game on Ranges (Codeforces 1623B)
Tags: Implement, dfs and similar

Alice and Bob play the following game. Alice has a set $$$S$$$ of disjoint ranges of integers, initially containing only one range $$$[1, n]$$$. In one turn, Alice picks a range $$$[l, r]$$$ from the set $$$S$$$ and asks Bob to pick a number in the range. Bob chooses a number $$$d$$$ ($$$l \le d \le r$$$). Then Alice removes $$$[l, r]$$$ from $$$S$$$ and puts into the set $$$S$$$ the range $$$[l, d - 1]$$$ (if $$$l \le d - 1$$$) and the range $$$[d + 1, r]$$$ (if $$$d + 1 \le r$$$). The game ends when the set $$$S$$$ is empty. We can show that the number of turns in each game is exactly $$$n$$$.After playing the game, Alice remembers all the ranges $$$[l, r]$$$ she picked from the set $$$S$$$, but Bob does not remember any of the numbers that he picked. But Bob is smart, and he knows he can find out his numbers $$$d$$$ from Alice's ranges, and so he asks you for help with your programming skill.Given the list of ranges that Alice has picked ($$$[l, r]$$$), for each range, help Bob find the number $$$d$$$ that Bob has picked.We can show that there is always a unique way for Bob to choose his number for a list of valid ranges picked by Alice.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).Each of the next $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), denoting the range $$$[l, r]$$$ that Alice picked at some point.Note that the ranges are given in no particular order.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the ranges for each test case are from a valid game.

Output: For each test case print $$$n$$$ lines. Each line should contain three integers $$$l$$$, $$$r$$$, and $$$d$$$, denoting that for Alice's range $$$[l, r]$$$ Bob picked the number $$$d$$$.You can print the lines in any order. We can show that the answer is unique.It is not required to print a new line after each test case. The new lines in the output of the example are for readability only. 

Note: In the first test case, there is only 1 range $$$[1, 1]$$$. There was only one range $$$[1, 1]$$$ for Alice to pick, and there was only one number $$$1$$$ for Bob to pick.In the second test case, $$$n = 3$$$. Initially, the set contains only one range $$$[1, 3]$$$.   Alice picked the range $$$[1, 3]$$$. Bob picked the number $$$1$$$. Then Alice put the range $$$[2, 3]$$$ back to the set, which after this turn is the only range in the set.  Alice picked the range $$$[2, 3]$$$. Bob picked the number $$$3$$$. Then Alice put the range $$$[2, 2]$$$ back to the set.  Alice picked the range $$$[2, 2]$$$. Bob picked the number $$$2$$$. The game ended. In the fourth test case, the game was played with $$$n = 5$$$. Initially, the set contains only one range $$$[1, 5]$$$. The game's turn is described in the following table.  Game turnAlice's picked rangeBob's picked numberThe range set afterBefore the game start$$$ \{ [1, 5] \} $$$1$$$[1, 5]$$$$$$3$$$$$$ \{ [1, 2], [4, 5] \}$$$2$$$[1, 2]$$$$$$1$$$$$$ \{ [2, 2], [4, 5] \} $$$3$$$[4, 5]$$$$$$5$$$$$$ \{ [2, 2], [4, 4] \} $$$4$$$[2, 2]$$$$$$2$$$$$$ \{ [4, 4] \} $$$5$$$[4, 4]$$$$$$4$$$$$$ \{ \} $$$ (empty set) 

Sample Inputs:
4
1
1 1
3
1 3
2 3
2 2
6
1 1
3 5
4 4
3 6
4 5
1 6
5
1 5
1 2
4 5
2 2
4 4

Sample Outputs:
1 1 1

1 3 1
2 2 2
2 3 3

1 1 1
3 5 3
4 4 4
3 6 6
4 5 5
1 6 2

1 5 3
1 2 1
4 5 5
2 2 2
4 4 4

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    pairs = [[*map(int, input().split())] for _ in range(n)]
    pairs = sorted(pairs, key=lambda x: abs(x[0] - x[1]))
    D = {tuple(pair): 0 for pair in pairs}
    known = set()
    changes = True
    for (a, b) in pairs:
        if a == b and a not in known:
            known.add(a)
            print(a, b, a)
        else:
            s = set(range(a, b + 1))
            pos = s.difference(known)
            if len(pos) == 1:
                el = pos.pop()
                known.add(el)
                print(a, b, el)
    print()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    lt = []
    for i in range(n):
        lt.append(list(map(int, input().split())))
    lt.sort(key=lambda x: x[1] - x[0])
    number = set()
    for (x, y) in lt:
        for num in range(x, y + 1):
            if num not in number:
                number.add(num)
                break
        print(x, y, num)

Solution (Python):
def solve():
    n = int(input())
    seq = []
    for _ in range(n):
        (l, r) = map(int, input().split())
        seq.append((l, r))
    seqS = set(seq)
    for (l, r) in seq:
        if l == r:
            print(f'{l} {r} {l}')
            continue
        elif (l + 1, r) in seqS:
            print(f'{l} {r} {l}')
            continue
        elif (l, r - 1) in seqS:
            print(f'{l} {r} {r}')
            continue
        else:
            for i in range(l, r + 1):
                if (l, i - 1) in seqS and (i + 1, r) in seqS:
                    print(f'{l} {r} {i}')
                    break
for i in range(int(input())):
    solve()