Intervals

// Template: sort by start, then sweep once, comparing each interval to the last one kept.
func sweepTemplate(intervals [][]int) [][]int {
	sorted := slices.Clone(intervals) // never reorder the caller's slice
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })

	var out [][]int
	for _, cur := range sorted {
		if len(out) == 0 || false /* 1. cur does NOT overlap out's last */ {
			out = append(out, cur) // 2. start a new group
		} else {
			// 3. cur overlaps: fold it into the last group (extend the end, drop it, ...)
		}
	}
	return out
}

// Merge: merge all overlapping intervals.
func Merge(intervals [][]int) [][]int {
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })

	out := [][]int{}
	for _, cur := range sorted {
		last := len(out) - 1
		if last < 0 || out[last][1] < cur[0] { // gap: no overlap
			out = append(out, []int{cur[0], cur[1]})
		} else { // overlap (touching counts): extend the end
			out[last][1] = max(out[last][1], cur[1])
		}
	}
	return out
}

// Insert: insert newInterval into sorted, non-overlapping intervals and merge.
// No sorting needed: three phases — before, overlapping, after.
func Insert(intervals [][]int, newInterval []int) [][]int {
	out := [][]int{}
	i, n := 0, len(intervals)
	for i < n && intervals[i][1] < newInterval[0] { // entirely before
		out = append(out, intervals[i])
		i++
	}
	merged := []int{newInterval[0], newInterval[1]}
	for i < n && intervals[i][0] <= merged[1] { // overlaps: absorb
		merged[0] = min(merged[0], intervals[i][0])
		merged[1] = max(merged[1], intervals[i][1])
		i++
	}
	out = append(out, merged)
	for ; i < n; i++ { // entirely after
		out = append(out, intervals[i])
	}
	return out
}

// EraseOverlapIntervals: fewest intervals to remove so the rest do not overlap.
// Greedy: sort by END, keep every interval that starts at or after the last kept end.
func EraseOverlapIntervals(intervals [][]int) int {
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[1], b[1]) })

	kept, end := 0, 0
	for i, iv := range sorted {
		if i == 0 || iv[0] >= end {
			kept++
			end = iv[1]
		}
	}
	return len(sorted) - kept
}

// MinMeetingRooms: minimum rooms so no two overlapping meetings share one.
// Sweep line: sort starts and ends separately; a start before the next end needs a new room.
func MinMeetingRooms(intervals [][]int) int {
	n := len(intervals)
	starts, ends := make([]int, n), make([]int, n)
	for i, iv := range intervals {
		starts[i], ends[i] = iv[0], iv[1]
	}
	slices.Sort(starts)
	slices.Sort(ends)

	rooms, best, e := 0, 0, 0
	for _, s := range starts {
		for e < n && ends[e] <= s { // meetings that ended by s free their room
			rooms--
			e++
		}
		rooms++
		best = max(best, rooms)
	}
	return best
}

// CanAttendMeetings: true if no two meetings overlap.
func CanAttendMeetings(intervals [][]int) bool {
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
	for i := 1; i < len(sorted); i++ {
		if sorted[i][0] < sorted[i-1][1] {
			return false
		}
	}
	return true
}