Non-Overlapping Intervals.

Given a collection of intervals, represented as pairs of integers [start, end], where start denotes the start time of the interval and end denotes the end time of the interval. Find the minimum number of intervals that need to be removed in order to make the remaining intervals non-overlapping.

Example:

Input:

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

Output:

1

Explanation: In the input, the intervals [1, 2] and [2, 3] overlap, so we can remove either of them to make the remaining intervals non-overlapping. Thus, the minimum number of intervals to remove is 1.

Solution in C++:

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

// Function to find the minimum number of intervals to remove
int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // Sort the intervals based on their end time in ascending order
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });

    int end = intervals[0][1];
    int count = 1; // Number of non-overlapping intervals

    // Iterate through the sorted intervals
    for (int i = 1; i < intervals.size(); ++i) {
        // If the current interval does not overlap with the previous interval, increment the count and update the end time
        if (intervals[i][0] >= end) {
            ++count;
            end = intervals[i][1];
        }
    }

    // The minimum number of intervals to remove is the total number of intervals minus the non-overlapping ones
    return intervals.size() - count;
}

int main() {
    std::vector<std::vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};

    int result = eraseOverlapIntervals(intervals);
    std::cout << "Minimum number of intervals to remove: " << result << std::endl;

    return 0;
}

Explanation:

1. The eraseOverlapIntervals function takes a reference to a vector of vectors intervals.
2. We first handle the edge case where the intervals vector is empty. If it’s empty, there are no intervals to remove, so we return 0.
3. We sort the intervals vector based on their end time in ascending order using a custom comparator. This helps us find the non-overlapping intervals efficiently.
4. We initialize two variables end and count. The end variable represents the end time of the previously considered interval, and the count variable represents the number of non-overlapping intervals.
5. We iterate through the sorted intervals starting from the second interval. For each interval, we check if its start time is greater than or equal to the end time. If this condition holds, it means the current interval does not overlap with the previous one. In this case, we increment the count and update the end to be the end time of the current interval.
6. After processing all intervals, the count will be the number of non-overlapping intervals.
7. The minimum number of intervals to remove is the total number of intervals minus the non-overlapping ones, so we return intervals.size() - count.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the number of intervals in the input vector intervals. The main factor in the time complexity is the sorting step, which takes O(n log n) time using std::sort.

Space Complexity:

The space complexity of this solution is O(1). We use a constant amount of additional space to store variables end and count, and the sorting is done in-place within the given vector intervals.