Intervals and Sweep Lines
Interval overlap is reported at several firms in different disguises: the maximum number of concurrent active windows, order intervals with cancellations, event scheduling. It is a small family with one idea in it, and once you have the idea the problems differ only in what you accumulate.
Stop thinking about intervals
An interval is awkward because it is two numbers that have to be considered together. Turn it into two events that can be considered separately:
Sort all events by position and walk them left to right, maintaining a running count. That count is the number of intervals covering the current point, and almost every question in the family is a function of it.
- Maximum concurrent. Track the largest value the counter reaches.
- Total covered length. Accumulate distance while the counter is above zero.
- Points covered by exactly . Accumulate distance while the counter equals .
- Any overlap at all. Report as soon as the counter exceeds one.
- Merge overlapping intervals. Emit a merged interval each time the counter returns to zero.
The rest of this lesson is for subscribers
Unlock every lesson in Programming for Quantitative Developers, and every other premium course.
Subscribe to continueTest your knowledge
Keep reading Programming for Quantitative Developers
25 lessons in this course, and every other premium course, on one subscription.
- Every lesson in every course, with the worked examples and interactive simulators
- Graded questions on every lesson, with explanations for the wrong answers as well as the right one
- The trainers, timed assessments and brainteaser library that go with them