educative.io

Educative

Find all conflicting appointments?

For the “find all conflicting appointments”, can you give some hints on how to solve this without O(n^2)? I’ve seen everything from binary search to using an Interval Tree.

Thanks.

Actually figured it out ! Similar pattern as you indicate. We just need to track the interval that contributes the conflicting ‘end’.

I don’t think there’s a solution better than O(n^2), since in worst case it’s possible that every pair in the intervals has a conflict. Am I right?

There is a better solution.
Look at “Problem challenge 1”