To solve the problem of finding the maximum number of non-overlapping intervals, we can follow a greedy approach. Here's the step-by-step solution:
Approach
The key insight of the greedy algorithm is to select intervals that end the earliest—this leaves the maximum possible room for subsequent intervals, allowing us to fit more non-overlapping intervals.
Steps:
- Sort Intervals: First, sort the intervals based on their end times. This ensures we always consider the interval that finishes earliest next.
- Select Intervals: Start with the first interval (since it ends earliest). Then, for each subsequent interval, check if it starts after the end of the last selected interval. If yes, select it and update the last end time.
- Count: The number of selected intervals is the maximum number of non non0verlapping intervals.
Solution Code
def max_non_overlapping_intervals(intervals):
if not intervals:
return 0
# Sort intervals by their end time
intervals.sort(key=lambda x: x[1])
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
count += 1
last_end = end
return count
Explanation
Let’s take an example to see how this works:
- Input:
[[1,2], [2,3], [3,4], [1,3]] - Sorted by end:
[[1,2], [2,3], [1,3], [3,4]] - Selected intervals:
[1,2](first interval)[2,3](start 2 >= last end 2)[3,4](start3 >= last end3)
- Result: 3 (maximum non-overlapping intervals).
This approach runs in O(n log n) time (due to sorting) and O(1) space (excluding input storage), which is optimal for this problem.
Note: If the problem asks for the minimum number of intervals to remove to make all intervals non-overlapping, the answer is len(intervals) - max_non_overlapping_intervals(intervals).
Let me know if you need clarification on a different problem scenario!


作者声明:本文包含人工智能生成内容。