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.
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”