Intervals

An interval is a time range like a meeting from 9 to 10. Questions are about overlaps: can you attend all, how many rooms, how to merge. Almost always the first move is to sort by start time, then sweep once.

After this topic: You can sort and sweep, decide when two ranges overlap, and know when a heap or a greedy "earliest end" rule is needed.

Do these first: Heap / Priority Queue

0 of 6 solved0%

Step 1 · Read the lesson

Intervals

Sort by start, then sweep and merge overlapping ranges.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Insert IntervalMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func insert(intervals [][]int, newInterval []int) [][]int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Intervals lesson page.

// 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
}

2.Merge IntervalsMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func merge(intervals [][]int) [][]int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Intervals lesson page.

// 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
}

3.Non-overlapping IntervalsMedium
When two intervals overlap, which one is less harmful to keep?
Sort by end. Keep an interval if it starts at or after the last kept end; otherwise count a removal. (Keeping the earliest end leaves the most room.)
Target: O(n log n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func eraseOverlapIntervals(intervals [][]int) int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Intervals lesson page.
// 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 }
4.Meeting RoomsEasy
One person can attend all meetings only if no two overlap.
Sort by start and check that every meeting starts at or after the previous one ends.
Target: O(n log n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func CanAttendMeetings(intervals []*Interval) bool
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Intervals lesson page.
// 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 }

5.Meeting Rooms IIMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func MinMeetingRooms(intervals []*Interval) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Intervals lesson page.

// 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
}

6.Minimum Interval to Include Each QueryHard

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func minInterval(intervals [][]int, queries []int) []int

Tested with go test. Try it yourself first, then compare.

// MinInterval answers each query with the size of the smallest interval containing it, or -1.
// Process queries in increasing order. Push every interval that has started into a min-heap by size, and pop
// intervals that have already ended; the top of the heap is the answer.
func MinInterval(intervals [][]int, queries []int) []int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	order := make([]int, len(queries)) // query indexes sorted by value, so answers go back in the original order
	for i := range order {
		order[i] = i
	}
	sort.Slice(order, func(a, b int) bool { return queries[order[a]] < queries[order[b]] })
	ans := make([]int, len(queries))
	h := &intervalHeap{}
	i := 0
	for _, qi := range order {
		q := queries[qi]
		for i < len(intervals) && intervals[i][0] <= q {
			heap.Push(h, [2]int{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]}) // {size, end}
			i++
		}
		for h.Len() > 0 && (*h)[0][1] < q {
			heap.Pop(h) // ended before the query
		}
		if h.Len() == 0 {
			ans[qi] = -1
		} else {
			ans[qi] = (*h)[0][0]
		}
	}
	return ans
}

type intervalHeap [][2]int

func (h intervalHeap) Len() int           { return len(h) }
func (h intervalHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h intervalHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *intervalHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *intervalHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}