arcbjorn

thoughtbook

RSS Feed

Sunday, February 26, 2023

Non-overlapping intervals

Leetcode 435 problem.

Go

  • Time complexity: O(nlog(n))O(n * log(n)) - n is a length of a string
  • Auxiliary space: O(1)O(1) - constant amount of time
func eraseOverlapIntervals(intervals [][]int) int {
    minimumIntervals, previous := 0, 0
    
    // sort in ascending order
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    for i := 1; i < len(intervals); i++ {
        currentIntervalStart := intervals[i][0]
        currentIntervalEnd := intervals[i][1]

        previousIntervalEnd := intervals[previous][1]

        if currentIntervalStart < previousIntervalEnd {
            if currentIntervalEnd < previousIntervalEnd {
                previous = i
            }

            minimumIntervals++
        } else {
            previous = i
        }
    }

    return minimumIntervals
}
Creative Commons Licence