algoadvance

Leetcode 435. Non

Problem Statement

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Each interval is defined as a pair of integers [start, end], representing the start and end times.

Clarifying Questions

  1. How are inputs given?
    • The inputs are given as a vector of pairs of integers. Each pair represents an interval.
  2. What are the constraints on the input?
    • All intervals are of form [start, end] where start <= end.
    • The number of intervals can range from 1 to 1000.
  3. What should be the output?
    • The output is a single integer, representing the minimum number of intervals that need to be removed.
  4. Are intervals inclusive or exclusive at their endpoints?
    • Typically, intervals are inclusive at both endpoints unless otherwise specified.

Strategy

The problem can be approached by sorting the intervals based on their ending times. Here’s why this strategy works:

Steps:

  1. Sort the intervals based on their ending times.
  2. Initialize a variable to track the end time of the last added interval.
  3. Iterate through the sorted intervals and count overlaps:
    • If the start time of the current interval is less than the end time of the last added interval, increment the removal counter.
    • Otherwise, update the end time of the last added interval to the end time of the current interval.
  4. Return the removal counter.

Code

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

using namespace std;

int eraseOverlapIntervals(vector<pair<int, int>>& intervals) {
    if (intervals.empty()) return 0;

    // Sort intervals based on their end times
    sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    int removals = 0;       // Counter for the number of intervals to remove
    int prev_end = intervals[0].second;  // End time of the last added interval

    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i].first < prev_end) {
            // If there is an overlap
            removals++;
        } else {
            // No overlap, update the end time of the last added interval
            prev_end = intervals[i].second;
        }
    }

    return removals;
}

int main() {
    // Example usage
    vector<pair<int, int>> intervals = \{\{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    cout << "Minimum number of intervals to remove: " << eraseOverlapIntervals(intervals) << endl;
    return 0;
}

Time Complexity

The time complexity of this solution is (O(n \log n)), where (n) is the number of intervals. This is due to the sorting step. The subsequent iteration through the intervals is (O(n)), making the overall complexity (O(n \log n)).

Together, these result in (O(n \log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI