LeetCode: Non-overlapping Intervals

Posted on January 10, 2018July 26, 2020 by braindenny

Non-overlapping Intervals

Similar Problems:

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

Note:
You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

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

Example 2:
Input: [ [1,2], [1,2], [1,2] ]

Output: 2

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

Example 3:
Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/non-overlapping-intervals
// Basic Ideas: greedy + heap
//
// Sort by intervals by starting points
// Greedy: If two intervals overlapping, remove the one ends later
//
// Complexity: Time O(n*log(n)), Space O(n)
import ("sort"
        "container/heap")

// max heap
type MyNode struct {
    x, y int
}

type MyHeap []MyNode
func (h MyHeap) Len() int {
    return len(h)
}
func (h MyHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h MyHeap) Less(i, j int) bool {
    return h[i].y > h[j].y
}

func (h *MyHeap) Push(x interface{}) {
    *h = append(*h, x.(MyNode))
}
func (h *MyHeap) Pop() interface{} {
    res := (*h)[len(*h)-1]
    *h = (*h)[0:len(*h)-1]
    return res
}

func min(x, y int) int {
    if x<y {
        return x
    } else {
        return y
    }
}

func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    res := 0
    h := &MyHeap{}
    heap.Init(h)
    for _, interval := range intervals {
        // Check whether need to remove intervals
        if h.Len()==0 {
            heap.Push(h, MyNode{x:interval[0], y:interval[1]})
        } else {
            // there would be only one conflict each time
            interval2 := heap.Pop(h).(MyNode)
            x1, y1 := interval[0], interval[1]
            x2, y2 := interval2.x, interval2.y
            if min(y1, y2) > max(x1, x2) {
                // overlap
                res++
                if y1 > y2 {
                    heap.Push(h, interval2)
                } else {
                    heap.Push(h, MyNode{x:interval[0], y:interval[1]})
                }
            } else {
                heap.Push(h, MyNode{x:interval[0], y:interval[1]})
                heap.Push(h, interval2)
            }
        }
    }
    return res
}

Post Views: 8