Editorial for BSSPC '21 J2 - James and Youtube

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sushi

This problem is asking for overlapping ranges; if any of the $N$ $N$ Youtube sessions ranges overlap with the $M$ $M$ class ranges.

This can be done easily by using a boolean array $v[i]$ $v [i]$ . $v[i]$ $v [i]$ is true if any class is happening on the $i^\text{th}$ $i^{th}$ minute, and false otherwise. Then for each of the Youtube ranges given, loop through the range and check if $v[i]$ $v [i]$ is true for any $i$ $i$ within that range. If any $v[i]$ $v [i]$ is true, then there are overlap(s), otherwise there aren't any overlap(s).

The time complexity is $\mathcal O(1440 \times (N+M))$ $O (1440 \times (N + M))$ .

Alternatively, you can store the ranges and use $\mathcal O(1)$ $O (1)$ overlap checking functions. This can be done in $\mathcal O(NM)$ $O (N M)$ time.

Time Complexity: $\mathcal O(1440 \times (N+M))$ $O (1440 \times (N + M))$ or $\mathcal O(NM)$ $O (N M)$ , depending on implementation.

Comments

There are no comments at the moment.