Merge Intervals algorithm

article.go

package merge_intervals

import (
	"container/heap"
)

type Slot struct {
	Start int
	Stop  int
}

// Merge two arrays of time slots.
func Merge(arr1, arr2 []Slot) []Slot {
	out := make([]Slot, 0)
	i1, i2 := 0, 0
	for i1 < len(arr1) && i2 < len(arr2) {
		v1, v2 := arr1[i1], arr2[i2]

		overlap12 := (v2.Start >= v1.Start) && (v2.Start <= v1.Stop)
		overlap21 := (v1.Start >= v2.Start) && (v1.Start <= v2.Stop)
		if overlap12 || overlap21 {
			merged := Slot{
				Start: min(v1.Start, v2.Start),
				Stop:  max(v1.Stop, v2.Stop),
			}
			if v1.Stop < v2.Stop {
				arr2[i2] = merged
				i1++
			} else {
				arr1[i1] = merged
				i2++
			}
			continue
		}

		// no overlap; save the earliest of the intervals
		if v1.Stop < v2.Stop {
			out = append(out, v1)
			i1++
		} else {
			out = append(out, v2)
			i2++
		}
	}

	out = append(out, arr1[i1:]...)
	out = append(out, arr2[i2:]...)

	return out
}

// given an array of occupied time slots,
// returns available time slots in range from 1 to 12.
func inverseSchedule(schedule []Slot) []Slot {
	start := 1
	var out []Slot
	for ind, appointment := range schedule {
		if ind == 0 && appointment.Start == 1 {
			start = appointment.Stop
			continue
		}
		out = append(out, Slot{Start: start, Stop: appointment.Start})
		start = appointment.Stop
	}
	if start < 12 {
		out = append(out, Slot{Start: start, Stop: 12})
	}
	return out
}

// AvailableSlots for all employees.
// Working hours starts at 1 ends at 12.
func AvailableSlots(schedule [][]Slot) []Slot {
	if len(schedule) == 0 {
		return []Slot{{1, 12}}
	}
	if len(schedule) == 1 {
		return inverseSchedule(schedule[0])
	}
	merged := Merge(schedule[0], schedule[1])
	for _, s := range schedule[2:] {
		merged = Merge(merged, s)
	}

	return inverseSchedule(merged)
}