Interval Scheduling
Interval scheduling is a fundamental algorithmic technique used to select the maximum number of non-overlapping intervals or schedule resources optimally. This pattern is crucial for time management problems, resource allocation, and optimizing schedules in various applications.
An interval is defined by a start time and end time, usually represented as [start, end]. The goal is typically to:
- Select maximum non-overlapping intervals - Choose as many intervals as possible without conflicts
- Schedule with minimum resources - Use fewest resources to cover all intervals
- Minimize dissatisfaction - For weighted intervals with importance
Real-World Analogy
Think of interval scheduling like planning your day with meetings. You have multiple meeting requests with different start and end times, and you want to attend as many meetings as possible without any conflicts. The key insight is that if you always choose the meeting that ends earliest, you’ll have the most flexibility to fit in additional meetings later.
Visual Explanation
Let’s visualize how the greedy algorithm works:
Input Intervals: [1,4], [2,5], [6,8], [7,9]
Step 1: Sort by end time
Sorted: [1,4], [2,5], [6,8], [7,9]
Step 2: Greedy selection
lastEnd = -∞
Process [1,4]: 1 >= -∞ ✓ → Select [1,4], lastEnd = 4
Process [2,5]: 2 < 4 ✗ → Skip [2,5]
Process [6,8]: 6 >= 4 ✓ → Select [6,8], lastEnd = 8
Process [7,9]: 7 < 8 ✗ → Skip [7,9]
Result: [1,4], [6,8]The algorithm sorts intervals by their end times and greedily selects the earliest finishing interval that doesn’t conflict with previously selected intervals.
When to Use This Pattern
Use interval scheduling when you encounter problems with these characteristics:
- Input consists of intervals with start and end times
- Need to select maximum number of non-overlapping intervals
- Looking for optimal resource allocation
- Time-based constraints are involved
- Greedy approach is applicable (no need for complex backtracking)
Complexity Analysis
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Activity Selection | O(n log n) | O(1) | Unweighted intervals |
| Weighted Selection | O(n²) | O(n) | Weighted intervals |
| Min Resources | O(n log n) | O(n) | Resource scheduling |
Common Mistakes
- Wrong sorting order - Sorting by start instead of end time
- Incorrect overlap checking - Not considering half-open intervals properly
- Missing edge cases - Empty arrays, single intervals
- Resource counting - Not properly tracking concurrent intervals
Next Steps
Ready to dive deeper? Check out our code templates for reusable implementations and practice problems to apply these concepts.