435. Non-overlapping Intervals

Description of the Problem

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4

The problem is equivalent to classical Activity Selection Problem which is to maximise the number of compatiable activities. Thus, in the following explanation, we assume that our goal is to maximise the number of activities in our schdule.

To solve the above problem, we choose activities one-by-one with earliest finish time (Greedy Algorithm).

Optimal Substructure Property

Suppose an activity \(a_k\) with interval \((s_k, f_k)\) is in optimal schedule from \(f_i\) to \(s_j\). The optimal solution can be divided into 3 parts: \( A_{ik} \cup a_k \cup A_{kj} \) where \( A_{ik} \) is optimal schedule start after \(f_i\) and finsih before \(s_k\) and \( A_{kj} \) is optimal schedule start after \(f_k\) and finsih before \(s_j\).

In other word, we can use Divide-and-Conquer to find optimal solution. i.e. choose an activity \(a_k\) such that the combined solution is maximum.

\[ \arg\max_{k} | A_{0k} \cup a_k \cup A_{kn} | \]

Greedy-choice Property

Suppose we have an optimal schedule \(A^*\) contains \(a_k\) which has earliest finish time in \( A^* \).

Suppose \( a_j \) has earliest finish time in the set of activities.

Replace \( a_k \) by \( a_j \) still yield the optimal schedule.

Code (Java)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (ai, aj) ->  ai[1] - aj[1]);
        int count = 0;
        final int [] prev = intervals[0];
        int prev_start = prev[0];
        int prev_end = prev[1];

        for(int i = 1; i < intervals.length; i++){
            int[] curr = intervals[i];
            int curr_start = curr[0];
            int curr_end = curr[1];
            if(curr_start < prev_end ){
                count ++;
            }
            else{
                prev_start = curr_start;
                prev_end = curr_end;
            }
        }

        return count;
    }
}

Complexity

Time complexity:

\(O(n\lg n + n)\)
- Sorting + Selection

Auxiliary Space:

\( O(1) \)

Further Discussion

It is absolutely a bad way to implement a tuple (a, b) by Array. Especially since Rust support tuples, storing two number (start time and finish time) in Vector is not the good practice. The following code is alternative implementation and solution.

type Interval = (i32, i32);

struct Solution{}

impl Solution {
    pub fn erase_overlap_intervals(intervals: Vec<Interval>) -> i32 {
        let mut intervals = intervals;
        intervals.sort_by( |(_,f1), (_,f2)| f1.cmp(&f2) );
        let mut count = 0;
        let (mut prev_start, mut prev_end) = intervals[0];
        for (curr_start, curr_end) in intervals.into_iter().skip(1) {
            if curr_start < prev_end {
                count += 1;
            }
            else{
                prev_start = curr_start;
                prev_end = curr_end;
            }
        }

        return count;
    }
}


fn main(){
    println!("{}", Solution::erase_overlap_intervals( vec![(1,2),(2,3),(3,4),(1,3)] ) );
    println!("{}", Solution::erase_overlap_intervals( vec![(1,2),(1,2),(1,2)] ) );
    println!("{}", Solution::erase_overlap_intervals( vec![(1,2),(2,3)] ) );
}

Leetbook