To solve the problem of finding the maximum number of non-overlapping intervals, we can use a greedy algorithm. The key insight is to always select the interval that ends the earliest, as this leaves the maximum remaining time for subsequent intervals.
Approach
- Sort Intervals: First, sort the intervals based on their end times in ascending order. This allows us to always pick the interval that ends the earliest.
- Select Non-overlapping Intervals:
- Start with the first interval (since it ends the earliest).
- For each subsequent interval, check if it starts after the end of the last selected interval. If it does, select this interval and update the end time of the last selected interval.
- Count Selected Intervals: Keep a count of the selected non-overlapping 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
- Sorting: By sorting intervals by their end times, we ensure that we always consider the interval that frees up time the earliest for other intervals.
- Greedy Selection: Each time we select an interval, we check if the next interval starts after the current interval ends. This ensures no overlaps and maximizes the number of intervals we can select.
- Efficiency: The sorting step takes (O(n \log n)) time, and the subsequent iteration takes (O(n)) time, making the overall time complexity (O(n \log n)), which is optimal for this problem.
This approach efficiently finds the maximum number of non-overlapping intervals using a greedy strategy, ensuring optimal performance and correctness.
Answer: The function max_non_overlapping_intervals returns the maximum number of non-overlapping intervals. For example, if the input is [[1,2],[2,3],[3,4],[1,3]], the output is 3. The final answer depends on the input intervals, but the code above correctly computes it.
\boxed{3} (for the example mentioned) or the result from the function for the given input. If the input is not provided, the code is the solution. However, if the problem expects a specific answer, please provide the input intervals. Assuming a common test case, the answer is \boxed{3}.


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