B - Intersection Editorial by en_translator


Since \(A_i\) and \(B_i\) are between \(1\) and \(1000\) (inclusive), \(x\) should be between \(1\) and \(1000\), too.
Therefore, it is sufficient to check for each \(x\) if it actually satisfies the given \(N\) conditions.

As another solution, the conditions where \(x\) should satisfy is equivalent to \(\max(A_1, A_2, A_3, \dots, A_N) \le x\le \min(B_1, B_2, B_3, \dots, B_N)\), so the answer can be found as \(\max(0, \min(B_1, B_2, B_3, \dots, B_N) - \max(A_1, A_2, A_3, \dots, A_N) + 1)\).
The complexity of the first solution is \(\Theta (N \max{B_i})\), while the other is \(\Theta(N)\), which is faster.

Sample Code (C)

#include <stdio.h>
#include <stdbool.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int a[n];
	for (int i = 0; i < n; i++) a[i] = ri();
	int b[n];
	for (int i = 0; i < n; i++) b[i] = ri();
	
	int res = 0;
	for (int i = 1; i <= 1000; i++) {
		bool ok = true;
		for (int j = 0; j < n; j++) if (i < a[j] || i > b[j]) ok = false;
		if (ok) res++;
	}
	
	printf("%d\n", res);
	return 0;
}

Sample Code (Python)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

res = 0
for i in range(1, 1001) :
	ok = True
	for j in range(n) :
		if i < a[j] or i > b[j] : ok = False
	if ok : res += 1

print(res)

posted:
last update: