educative.io

Find the max number of intersections

isn’t it more efficient to find the max number of intervals that have intersection at the same time. That way space complexity is less. Because we only need space for sorting? What am I missing here please?

What you are missing is that when meetings overlap, each of them ends at a different time and you need to keep track of their end times in order to correctly calculate concurrent meetings.

In your implementation, you update end (the end of the current meeting) to be the minimum of two conflicting meetings. Thereby you are ignoring the fact that the longer meeting may be ongoing when you reach your value of end, and you will not account for it still requiring a room.

Also the space complexity is not really improved. It is O(nlogn) due to sorting. The additional O(nlogn) for the heap in the suggested solution does not change this complexity (even though, yes, it would require more space).