 # TWORANGES - Editorial

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Given two ranges [A, B] and [C, D]; count the number of integers contained in their union.

# EXPLANATION:

Notice that the bounds on the ranges are quite small; between 1 and 8.
This means the union of the ranges is also a subset of \{1, 2, 3, 4, 5, 6, 7, 8\}.

So, for each integer from 1 to 8, check whether it belongs to one of the ranges.
That is, for each 1 \leq x \leq 8, check at least one of

• A \leq x \leq B; or
• C \leq x \leq D

is true.
The number of x satisfying this condition is the answer.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

Code (Python)
for _ in range(int(input())):
a, b, c, d = map(int, input().split())
ans = 0
for i in range(1, 9):
if a <= i <= b or c <= i <= d: ans += 1
print(ans)

t=int(input())
for i in range(t):
a,b,c,d=map(int,input().split())
l1=set(range(a,b+1))
l2=set(range(c,d+1))
l=l1.union(l2)
print(len(l))


This method too works right?

Yes, pretty much any method to find the union of two sets will also work for this problem, since the constraints are so small.

1 Like

So say I am going to make the constrains larger. In that case how can we code the thing?

Using the fact that they’re intervals, you can solve the problem in \mathcal{O}(1) time with a little casework.

If [A, B] and [C, D] are disjoint intervals, the length of their union is just the sum of their lengths, i.e, (B-A+1) + (C-D+1).
If they intersect each other, the union is a single interval, which equals [\min(A, C), \max(B, D)]; the length of this is just \max(B, D) - \min(A, C) + 1.

Checking whether they intersect or not is quite simple, just see whether B lies in [C, D] or D lies in [A, B].

2 Likes