Non-Overlapping intervals program

Overview

An array of intervals is given where intervals[i] = [starti, endi]. We have to find out the minimum number of intervals to remove so that the interval in the intervals array become non-overlapping

Let’s understand it with an example

Input: intervals = [[2,3],[3,4],[4,5],[2,4]]
Output: 1
Explanation: [2,4] can be removed and the rest of the intervals are non-overlapping.

The idea is to first sort based interval start time and then count the overlapping intervals.

Program

Here is the program for the same.

package main

import (
	"fmt"
	"sort"
)

func eraseOverlapIntervals(intervals [][]int) int {
	lenIntervals := len(intervals)

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	prevIntervalEnd := intervals[0][1]

	minIntervals := 0
	for i := 1; i < lenIntervals; i++ {
		currentIntervalStart := intervals[i][0]
		currentIntervalEnd := intervals[i][1]

		if currentIntervalStart < prevIntervalEnd {
			minIntervals++
			if prevIntervalEnd >= currentIntervalEnd {
				prevIntervalEnd = currentIntervalEnd
			}
		} else {
			prevIntervalEnd = currentIntervalEnd
		}
	}
	return minIntervals
}

func main() {

	output := eraseOverlapIntervals([][]int{{2, 3}, {3, 4}, {4, 5}, {2, 4}})
	fmt.Println(output)
}

Output

6
13