The classic Interval Scheduling Problem has a well-known, simple O(n) greedy solution.
But what if the problem becomes more complex? Imagine solving k Interval Scheduling Problems, each with n/k unique independent intervals and n shared intervals across all k problems.
Can you design an algorithm that beats the naïve O(kn) approach?

Fortunately, I managed to discover an O(nlogn) solution—drawing inspiration from Lowest Common Ancestor (LCA) algorithms—and implemented it just in time, earning me an award.

SCPC is widely recognized as the largest and most prestigious competitive programming event in Korea. To learn more about the competition, please visit: