Problem B
Co-scheduling Analysis
In 2018, researchers discovered vulnerabilities in modern CPUs that allowed threads to steal each other’s data when running simultaneously on the same core during a solar eclipse, called ecliptic co-scheduling. Although no one understands how a solar eclipse could affect CPUs, at least they can study and prevent co-scheduling to try to mitigate the issue.
Cloud providers in particular are concerned with co-scheduling of threads from different cloud customers. The cloud provider you’re working for is designing ways to avoid co-scheduling and would like to understand how well their solutions work. Given a record of execution times for a collection of threads on a CPU’s core, they would like to know the total amount of co-scheduling between different threads that occurred, that is, the total amount of time for which two or more threads were running on the CPU at the same time.
Input
The first line of input consists of a single integer $M$ ($1 \leq M \leq 10^5$), which indicates the total number of running threads. Each of the following $M$ lines corresponds to a thread; the $i$th line records the intervals during which the $i$th thread was running. Each such line begins with an integer $k$ ($0 \leq k \leq 10^5$), the number of intervals, followed by $2k$ space-separated integers in the range $[0,10^9]$. The $2k$ integers are in strictly increasing order, and each consecutive pair denotes the start and end times, in seconds, of an interval during which the thread was running.
The total number of intervals across all threads will be at most $10^5$.
Output
Output the total number of seconds of co-scheduling as a single integer, that is, the total number of seconds during which two or more threads were running at the same time. Note that if one thread stops at the exact same time that another thread starts, that counts as zero seconds of co-scheduling.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 0 4 1 2 5 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 0 8 12 13 2 2 4 12 13 3 0 4 7 8 10 11 |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 0 4 1 4 8 1 8 12 |
0 |
