06 · СОРТИРОВКА

Интервалы

После сортировки по началу большинство задач сводятся к одному линейному проходу.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Сортировка

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

sort.Slice изменяет входной слайс.

Интервал

type Interval struct { Start, End int }

Структура читается лучше, но LeetCode обычно даёт [][]int.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Слияние интервалов

Сравниваем начало с концом последнего результата.

O(n log n) time · O(n) output

solution.go

func merge(a [][]int) [][]int {
    sort.Slice(a, func(i, j int) bool { return a[i][0] < a[j][0] })
    out := [][]int{}
    for _, cur := range a {
        if len(out) == 0 || out[len(out)-1][1] < cur[0] {
            out = append(out, cur)
        } else {
            out[len(out)-1][1] = max(out[len(out)-1][1], cur[1])
        }
    }
    return out
}

ПРИМЕР РЕШЕНИЯ

Минимум стрел

Жадно выбираем самое раннее окончание.

O(n log n) time · O(1) space

solution.go

func findMinArrowShots(points [][]int) int {
    sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
    arrows, end := 0, 0
    for i, p := range points {
        if i == 0 || p[0] > end { arrows++; end = p[1] }
    }
    return arrows
}

ПРИМЕР РЕШЕНИЯ

Можно посетить все встречи

После сортировки соседние встречи не должны пересекаться.

O(n log n) time · O(1) space

solution.go

func canAttend(intervals [][]int) bool {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[i-1][1] { return false }
    }
    return true
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Уточни: границы включительные или нет
Сначала подумай о сортировке
Разделяй пересечение и касание