Sunday, February 26, 2023
Non-overlapping intervals
Go
- Time complexity: -
n
is a length of a string - Auxiliary space: - 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
}