Non Overlapping Intervals in C++ (O(n log n) Time Complexity)

Given a collection of intervals, find the maximum number of non-overlapping intervals you can select.

Example 1:

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

Note:

You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Understanding the Problem

The core challenge of this problem is to select the maximum number of non-overlapping intervals from a given set of intervals. This problem is significant in various applications such as scheduling, where we need to maximize the number of non-conflicting tasks or events.

Potential pitfalls include misunderstanding the definition of non-overlapping intervals. Intervals that touch at the borders (e.g., [1,2] and [2,3]) are considered non-overlapping.

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. This approach ensures that we leave as much room as possible for subsequent intervals.

Naive Solution

A naive solution would involve checking all possible subsets of intervals to find the maximum number of non-overlapping intervals. However, this approach is not feasible due to its exponential time complexity.

Optimized Solution

The optimized solution involves the following steps:

Sort the intervals based on their end times.
Iterate through the sorted intervals and select the interval if it does not overlap with the previously selected interval.

This approach ensures that we can find the maximum number of non-overlapping intervals in O(n log n) time complexity due to the sorting step.

Algorithm

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

Sort the intervals based on their end times.
Initialize a variable to keep track of the end time of the last selected interval.
Iterate through the sorted intervals and select an interval if its start time is greater than or equal to the end time of the last selected interval.
Update the end time of the last selected interval to the end time of the current interval.

Code Implementation


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find the maximum number of non-overlapping intervals
int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    // Sort intervals based on their end times
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    int count = 0;
    int end = INT_MIN;

    // Iterate through the sorted intervals
    for (const auto& interval : 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 the current interval
            end = interval[1];
            count++;
        }
    }

    return count;
}

int main() {
    vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    cout << "Maximum number of non-overlapping intervals: " << maxNonOverlappingIntervals(intervals) << endl;
    return 0;
}

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.

To test these edge cases, we can include them in our test cases.

Testing

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

Simple cases with a few intervals.
Cases with overlapping intervals.
Edge cases such as an empty list of intervals.

We can use standard testing frameworks such as Google Test for C++ to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem statement and constraints thoroughly.
Think about potential edge cases and how to handle them.
Consider different approaches and their time and space complexities.
Practice solving 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: