Editorial for BSSPC '21 J2 - James and Youtube - Olympiads Online Judge

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^\text{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))$ ~\mathcal O(1440 \times (N+M))~.

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

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

Comments

There are no comments at the moment.