Number of Groups
Contest: CodeCraft-22 and Codeforces Round 795 (Div. 2)
Difficulty rating: 2300
Tags: data structures, dfs and similar, dsu, graphs, greedy, sortings

You are given $$$n$$$ colored segments on the number line. Each segment is either colored red or blue. The $$$i$$$-th segment can be represented by a tuple $$$(c_i, l_i, r_i)$$$. The segment contains all the points in the range $$$[l_i, r_i]$$$, inclusive, and its color denoted by $$$c_i$$$:

- if $$$c_i = 0$$$, it is a red segment;
- if $$$c_i = 1$$$, it is a blue segment.

We say that two segments of different colors are connected, if they share at least one common point. Two segments belong to the same group, if they are either connected directly, or through a sequence of directly connected segments. Find the number of groups of segments.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of segments.

Each of the next $$$n$$$ lines contains three integers $$$c_i, l_i, r_i$$$ ($$$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$$$), describing the $$$i$$$-th segment.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print a single integer $$$k$$$, the number of groups of segments.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example there are $$$5$$$ segments. The segments $$$1$$$ and $$$2$$$ are connected, because they are of different colors and share a point. Also, the segments $$$2$$$ and $$$3$$$ are connected, and so are segments $$$4$$$ and $$$5$$$. Thus, there are two groups: one containing segments $$$\{1, 2, 3\}$$$, and the other one containing segments $$$\{4, 5\}$$$.

Example input:
2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4

Example output:
2
3

Editorial:
We will be using the starting and ending points of different segments to count the final answer. We maintain a Union-Find data structure (DSU) on size $$$n$$$ corresponding to the $$$n$$$ segments given as input. We store all the starting and ending points in a set. (example: If $$$2$$$ segments are $$$(0,10)$$$ and $$$(11, 12)$$$, we store $$${0,10,11,12}$$$ in a set irrespective of the color of the segment). We now iterate through these points in ascending order.
We maintain $$$2$$$ running sets corresponding to the $$$2$$$ colors. In these sets, we will store the segments for which the starting point has been reached while iterating through the set of points but the ending point hasn't been reached (ie: we store the segments that have started but not ended).
The algorithm works as follows:
If we are at a point $$$x$$$:
• If it corresponds to a segment's starting point:   We add that segment to the set corresponding to its color  We merge (DSU merge) this segment with all segments present in the set corresponding to the other color (since their ending point hasn't been reached yet).  We also erase all segments in the set corresponding to the other color except the one with the largest closing point value.
• We add that segment to the set corresponding to its color
• We merge (DSU merge) this segment with all segments present in the set corresponding to the other color (since their ending point hasn't been reached yet).
• We also erase all segments in the set corresponding to the other color except the one with the largest closing point value.
• If the point corresponds to a segment's ending point:   We delete the segment from the set corresponding to its color.
• We delete the segment from the set corresponding to its color.
Why can we delete the segments of color except for the one with the largest ending point if we encounter a starting point of the other color?
We are able to greedily pick the segment with the furthest ending point value because all segments of the same color in that set have been connected together by the segments of the other color. Hence, we can just work with the segments with the largest ending point value of both colors for each component that exists.