To solve this problem, we need to find the maximum number of non-overlapping intervals from a given collection of intervals. The optimal approach to this problem uses a greedy algorithm, which ensures we select the maximum number of non-overlapping intervals by always choosing the interval that ends the earliest. This leaves the maximum room for subsequent intervals, thus maximizing the count.

Approach

1. Edge Case Handling: If there are no intervals, return 0 immediately.
2. Sort Intervals: Sort the intervals based on their end times in ascending order. This allows us to always pick the interval that ends earliest first.
3. Greedy Selection:
   • Initialize the count of non-overlapping intervals to 1 (since we start with the first interval in the sorted list).
   • Track the end time of the last selected interval.
   • Iterate through the sorted intervals. For each interval, if its start time is greater than or equal to the end time of the last selected interval, select it and update the end time of the last selected interval.

Solution Code

def max_non_overlapping_intervals(intervals):
    if not intervals:
        return 0
    # Sort intervals by their end time
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 1
    last_end = sorted_intervals[0][1]
    for current_start, current_end in sorted_intervals[1:]:
        if current_start >= last_end:
            count += 1
            last_end = current_end
    return count

Explanation

• Sorting: By sorting intervals based on their end times, we ensure that we always consider the interval that frees up the earliest for subsequent intervals.
• Greedy Selection: This step ensures that we select the maximum number of non-overlapping intervals. For example, if we have intervals [[1,4], [2,3], [3,4]], sorting by end time gives [[2,3], [3,4], [1,4]]. We select [2,3] first, then [3,4], which are non-overlapping, giving a count of 2.

This approach has a time complexity of O(n log n) due to the sorting step, where n is the number of intervals. The space complexity is O(1) if we sort the intervals in place (or O(n) if we create a new sorted list, depending on the implementation). This is efficient and optimal for the problem.

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