Interval Trees
Interval trees store intervals and answer overlap queries. Find all intervals containing a point.
Lessons
1. Intro
Why interval trees matter
2. Interval Representation
How to store intervals
3. The Overlap Problem
Why brute force fails
4. Interval Tree Structure
Divide and conquer idea
5. Building the Tree
Recursive construction
6. Point Query
Finding intervals at point
7. Why Dual Sorting Works
The scanning trick
8. Problem - Merge Intervals
Classic interval problem
9. Merge Intervals: Sorting Approach
Sort then scan
10. Merge Intervals Solution
Implement your solution
11. Problem - Insert Interval
Merge with new interval
12. Insert Interval Approach
Three-phase scan
13. Insert Interval Solution
Implement your solution
14. Augmented BST Approach
Alternative structure
15. Maintaining maxHigh
Update during operations
16. Overlap Search in Augmented BST
Using maxHigh to prune
17. Finding All Overlaps
Report all results
18. Problem - Meeting Rooms
Check for conflicts
19. Meeting Rooms Solution
Sort and check adjacent
20. Problem - Meeting Rooms II
Minimum rooms needed
21. Meeting Rooms II: Event Sweep
Start and end events
22. Meeting Rooms II: Heap Approach
Track ending times
23. Meeting Rooms II Solution
Implement your solution
24. Problem - Range Module
Dynamic interval management
25. Range Module: TreeMap Approach
Ordered map of intervals
26. Range Module Solution
Implement your solution
27. Interval Scheduling Maximization
Select non-overlapping set
28. Problem - Non-overlapping Intervals
Minimum removals
29. Non-overlapping Solution
Greedy removal
30. Segment Tree for Intervals
Range queries on intervals
31. Coordinate Compression
Handling large ranges
32. 2D Interval Problems
Rectangles as interval pairs
33. Problem - Rectangle Area II
Union of rectangles
34. Rectangle Area: Sweep Line
Sweep with segment tree
35. Rectangle Area II Solution
Implement your solution
36. Interval Tree vs Segment Tree
When to use which
37. Stabbing Number Problem
Max coverage point
38. Interval Partitioning
Minimum groups
39. Quiz: Interval Trees
Test your understanding
40. Section Recap
What you learned