Part IV · Fundamental Algorithm Design Paradigms
22. Intervals, Events and Sweep-Line Algorithms
7 lessons•34 topics•Intermediate
7 of 7 lessons published
22.014 animated
Interval modeling
- Closed vs open intervals
- Half-open intervals
- Overlap definitions
- Interval normalization
- Sorting endpoints
22.026 animated
Fundamental interval problems
- Merge intervals
- Insert interval
- Erase overlaps
- Intersections
- Meeting rooms
- Interval scheduling
22.034 animated
Difference-array event sweep
- Start/end events
- Event ordering
- Active count
- Maximum concurrency
- Range coverage
22.045 animated
One-dimensional sweep line
- Coordinate sorting
- Maintain active set
- Line segment unions
- Coverage length
- Earliest conflict
22.054 animated
Two-dimensional sweep line
- Rectangle union outline
- Orthogonal intersections
- Closest pair sweep
- Ordered event sets
22.065 animated
Coordinate compression
- Rank mapping
- Compress large coordinates
- Duplicate preservation
- Inverse mapping
- Compressed interval updates
22.073 animated
Combined techniques
- Sweep + heap
- Sweep + Fenwick
- Sweep + segment tree
- Offline queries by right endpoint