Non Overlapping Intervals in Python (O(n log n) Time Complexity)

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3
Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.

Problem Definition

The problem requires finding the maximum number of non-overlapping intervals from a given collection of intervals.

Input:

• A list of intervals where each interval is represented as a list of two integers [start, end].

Output:

• An integer representing the maximum number of non-overlapping intervals.

Constraints and Assumptions:

• The end point of an interval is always greater than its start point.
• Intervals with touching borders do not overlap.

Example:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3
Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.

Understanding the Problem

The core challenge is to select the maximum number of intervals such that no two intervals overlap. This problem is significant in various applications such as scheduling, resource allocation, and event planning.

Potential pitfalls include misunderstanding the definition of non-overlapping intervals, especially when intervals touch at their borders.

Approach

To solve this problem, we can use a greedy algorithm. The idea is to always pick the interval that ends the earliest and does not overlap with the previously selected interval.

Naive Solution:

A naive solution would involve checking all possible combinations of intervals to find the maximum set of non-overlapping intervals. This approach is not optimal due to its high time complexity.

Optimized Solution:

The optimized solution involves sorting the intervals by their end times and then iterating through the sorted list to select non-overlapping intervals.

Steps to Derive the Optimized Solution:

1. Sort the intervals based on their end times.
2. Initialize a variable to keep track of the end time of the last selected interval.
3. Iterate through the sorted intervals and select an interval if it starts after the end time of the last selected interval.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Sort the intervals by their end times.
2. Initialize a variable `end` to negative infinity to keep track of the end time of the last selected interval.
3. Initialize a counter `count` to zero to count the number of non-overlapping intervals.
4. Iterate through the sorted intervals:
   • If the start time of the current interval is greater than or equal to `end`, select this interval.
   • Update `end` to the end time of the current interval.
   • Increment the `count` by one.
5. Return the `count` as the result.

Code Implementation

def max_non_overlapping_intervals(intervals):
    # Sort intervals by their end times
    intervals.sort(key=lambda x: x[1])
    
    # Initialize the end time of the last selected interval
    end = float('-inf')
    
    # Initialize the count of non-overlapping intervals
    count = 0
    
    # Iterate through the sorted intervals
    for interval in intervals:
        # If the start time of the current interval is greater than or equal to the end time of the last selected interval
        if interval[0] >= end:
            # Select this interval
            end = interval[1]
            # Increment the count
            count += 1
    
    return count

# Example usage
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(max_non_overlapping_intervals(intervals))  # Output: 3

Complexity Analysis

The time complexity of the optimized solution is O(n log n) due to the sorting step. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

• Empty list of intervals: The output should be 0.
• Intervals with the same start and end times: These should be handled correctly by the sorting step.

Examples of Edge Cases:

Input: []
Output: 0

Input: [[1,2],[2,3],[3,4],[1,3],[2,2]]
Output: 3

Testing

To test the solution comprehensively, include a variety of test cases:

• Simple cases with a few intervals.
• Complex cases with many intervals.
• Edge cases as discussed above.

Example Test Cases:

def test_max_non_overlapping_intervals():
    assert max_non_overlapping_intervals([[1,2],[2,3],[3,4],[1,3]]) == 3
    assert max_non_overlapping_intervals([]) == 0
    assert max_non_overlapping_intervals([[1,2],[2,3],[3,4],[1,3],[2,2]]) == 3
    assert max_non_overlapping_intervals([[1,5],[2,6],[3,7],[4,8]]) == 1
    print("All test cases pass")

test_max_non_overlapping_intervals()

Thinking and Problem-Solving Tips

When approaching such problems:

• Understand the problem requirements and constraints thoroughly.
• Think about different approaches and their time complexities.
• Start with a simple solution and then optimize it.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of finding the maximum number of non-overlapping intervals. We explored a greedy algorithm to solve the problem efficiently and provided a detailed explanation of the approach, algorithm, and code implementation. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Non-overlapping Intervals
• GeeksforGeeks: Activity Selection Problem
• Coursera: Algorithms Part I