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 Youtube sessions ranges overlap with the M class ranges.

This can be done easily by using a boolean array v[i]. v[i] is true if any class is happening on the i^\text{th} minute, and false otherwise. Then for each of the Youtube ranges given, loop through the range and check if v[i] is true for any i within that range. If any 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)).

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

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


Comments

There are no comments at the moment.