Satisfying Constraints (Codeforces 1920A)
Tags: Greedy, brute force

Alex is solving a problem. He has $$$n$$$ constraints on what the integer $$$k$$$ can be. There are three types of constraints:  $$$k$$$ must be greater than or equal to some integer $$$x$$$;  $$$k$$$ must be less than or equal to some integer $$$x$$$;  $$$k$$$ must be not equal to some integer $$$x$$$. Help Alex find the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints. It is guaranteed that the answer is finite (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). Also, it is guaranteed that no two constraints are the exact same.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of constraints.The following $$$n$$$ lines describe the constraints. Each line contains two integers $$$a$$$ and $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). $$$a$$$ denotes the type of constraint. If $$$a=1$$$, $$$k$$$ must be greater than or equal to $$$x$$$. If $$$a=2$$$, $$$k$$$ must be less than or equal to $$$x$$$. If $$$a=3$$$, $$$k$$$ must be not equal to $$$x$$$.It is guaranteed that there is a finite amount of integers satisfying all $$$n$$$ constraints (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). It is also guaranteed that no two constraints are the exact same (in other words, all pairs $$$(a, x)$$$ are distinct).

Output: For each test case, output a single integer — the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints.

Note: In the first test case, $$$k \geq 3$$$ and $$$k \leq 10$$$. Furthermore, $$$k \neq 1$$$ and $$$k \neq 5$$$. The possible integers $$$k$$$ that satisfy the constraints are $$$3,4,6,7,8,9,10$$$. So the answer is $$$7$$$.In the second test case, $$$k \ge 5$$$ and $$$k \le 4$$$, which is impossible. So the answer is $$$0$$$.

Sample Inputs:
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001

Sample Outputs:
7
0
90
0
0
800000000

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline

def inp():
    return int(input())

def inlst():
    return list(map(int, input().split()))

def instr():
    s = input()
    return list(s[:len(s) - 1])

def insep():
    return map(int, input().split())
n = inp()
for _ in range(n):
    c = inp()
    greater = []
    less = []
    equal = []
    for i in range(c):
        (t, x) = insep()
        if t == 1:
            greater.append(x)
        elif t == 2:
            less.append(x)
        else:
            equal.append(x)
    rem = 0
    lm = min(less)
    gm = max(greater)
    if gm > lm:
        print('0')
        continue
    for num in equal:
        if gm <= num <= lm:
            rem += 1
    print(lm - gm - rem + 1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        m = 0
        M = 10 ** 9
        arr = []
        for i in range(n):
            (a, b) = map(int, input().split())
            if a == 1:
                m = max(m, b)
            elif a == 2:
                M = min(M, b)
            else:
                arr.append(b)
        if m > M:
            print(0)
            continue
        ans = M - m + 1
        for i in arr:
            if m <= i <= M:
                ans -= 1
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import *
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solve():
    num_constraints = inp()
    l = 1
    r = 10 ** 9
    s = 0
    neq = []
    for _ in range(num_constraints):
        (a, x) = invr()
        if a == 1:
            l = max(l, x)
        elif a == 2:
            r = min(r, x)
        elif a == 3:
            neq.append(x)
    for x in neq:
        if l <= x <= r:
            s += 1
    print(max(r - l + 1 - s, 0))
if __name__ == '__main__':
    t = inp()
    for i in range(t):
        solve()