algoadvance

Leetcode 435. Non

Problem Statement

You are given an array of intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. 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.

Clarifying Questions

  1. Can the intervals be unsorted initially?
    • Yes, the intervals can be provided in any order.
  2. Are the interval boundaries inclusive or exclusive?
    • The intervals are inclusive of the start and end values.
  3. What is the range of the intervals?
    • There are no explicit constraints in the example, but typically the interval range will be within reasonable bounds for solving within typical computational limits.
  4. Can intervals have zero length (i.e., start_i == end_i)?
    • Yes, intervals can have zero length.

Code

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // Sort the intervals based on their end time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int end = intervals[0][1];
        int count = 0;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                // We need to remove this interval
                count++;
            } else {
                // Update the end to be the end of this interval
                end = intervals[i][1];
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        int[][] intervals1 = // use example above
        System.out.println(sol.eraseOverlapIntervals(intervals1)); // Output: 1

        int[][] intervals2 = // use example above
        System.out.println(sol.eraseOverlapIntervals(intervals2)); // Output: 2

        int[][] intervals3 = // use example above
        System.out.println(sol.eraseOverlapIntervals(intervals3)); // Output: 0
    }
}

Strategy

  1. Sort the Intervals by End Time:
    • Sorting the intervals by their end time allows us to always choose the interval that ends the earliest, maximizing the number of non-overlapping intervals.
  2. Greedy Approach:
    • Start with the first interval and check if the next interval starts before the current interval ends.
    • If it does, count this as an overlap and potentially removable.
    • Otherwise, update the end time to the current interval’s end time and continue.
  3. Count Overlaps:
    • For each overlapping interval found, increment the count.
    • The count will give the minimum number of intervals that need to be removed.

Time Complexity

Thus, the overall time complexity is O(n log n) due to the sorting step.

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