Non-overlapping Intervals

Problem statement

You are given a list of intervals [start, end). Return the minimum number of intervals to remove so that the rest do not overlap.

Example:

Input:

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

Expected output:

1

Why: remove [1, 3] and the remaining intervals are non-overlapping.

Practice on LeetCode: Non-overlapping Intervals

Golang Solution

Sort by end time (classic interval scheduling). Keep the earliest-finishing interval and skip (count as a removal) any later interval that starts before the kept one ends; when there’s no conflict, advance the kept pointer.

Time: O(n log n) — sorting
Space: O(1) extra beyond the sort

func eraseOverlapIntervals(intervals [][]int) int {

    sort.Slice(intervals, func(a, b int) bool {
        return intervals[a][1] < intervals[b][1]
    })
    ans := 0
    i := 0
    j := 1
    for j < len(intervals) && i < len(intervals) {
        if intervals[i][1] <= intervals[j][0] {
            i = j
            j += 1
        } else {
            j += 1
            ans += 1
        }
    }

    return ans
}