Non-overlapping Intervals

medium

Acceptance: 43%

IntervalsGreedySorting

Given a collection of intervals [start, end], find the smallest number of intervals to discard so that the remaining intervals are all mutually non-overlapping.

Examples

Example 1:

Input:intervals = [[1,3],[2,4],[3,5],[4,6]]

Output:1

Example 2:

Input:intervals = [[1,3],[1,3],[1,3]]

Output:2

Hints

import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] i : intervals) {
            if (i[0] >= end) {
                end = i[1];
            } else {
                count++;
            }
        }
        return count;
    }
}

Time complexityO(n log n)

Space complexityO(1)

Non-overlapping Intervals

Examples

Hints

Related Problems