Point with Maximum Overlapping Intervals

viaLeetCode

Problem: Given a list of intervals [start, end], find the first point in time where the number of overlapping intervals is at its maximum, and return that point.

Constraints: Number of intervals < 10^5.

Approach: Create events: +1 at each interval's start, -1 just after each interval's end. Sort all events by time (ties broken so starts are processed before ends at the same coordinate, per the problem's overlap definition), sweep through them accumulating a running counter, and track the point where the running counter first reaches its maximum value. O(n log n) due to sorting.

Add a follow-up question they asked
No follow-ups yet. Be the first to add one.
asked …
LeaderboardSalary
Language
Account