Метод точек

В этом уроке ты

Решишь задачу с собеседования в BigTech.
Освоишь “метод точек” для решения задач.

Пример задачи с собеседования

Представь, что ты заходишь на собеседование. Интервьюер уже готов и начинает озвучивать условие задачи…

Условие

Дан массив отрезков segments, где segments[i] содержит отрезок бронирования комнаты для переговоров: [начало бронирования, конец бронирования].

Нужно вернуть минимальное число переговорных комнат, которые понадобятся, чтобы все встречи могли состояться.

Пример 1

Ввод: segments = [[3,5],[2,5],[1,3],[6,7]]
Вывод: 2
Объяснение: в промежутке от 2 до 5 одновременно нужны 2 переговорные комнаты.

В момент времени 3 - сначала была освобождена комната, а потом сразу занята.

Пример 2

Ввод: segments = [[3,4],[1,100],[2,100]]
Вывод: 3

Идея решения

Преобразуем каждый отрезок [start, end] в две точки:
1. [start, +1] – сигнал, что нужна дополнительная комната
2. [end, -1] – сигнал, что комната освобождается
Сортируем все точки по их значению (при равных значениях первыми идут точки с -1).
Проходим по отсортированному массиву, используя счётчик:
1. При встрече +1 увеличиваем счётчик (занимаем комнату)
2. При встрече -1 уменьшаем счётчик (освобождаем комнату)
Максимальное значение счётчика во время прохода и будет ответом.

Например, при segments = [[3,5],[2,5],[1,3],[6,7]] в ходе преобразования в массив точек и сортировки получим массив:

Идя по нему с учётом +1 и -1, мы найдём максимальное значение счётчика — это и есть количество необходимых комнат.

Код

public class Solution
{
    public static int CountMeetingRooms(List<List<int>> segments)
    {
        List<List<int>> points = new List<List<int>>();
        foreach (var seg in segments)
        {
            // Точка начала отрезка, +1 - нужна ещё одна комната
            points.Add(new List<int> { seg[0], +1 });
            // Точка конца отрезка, -1 - комната освобождается
            points.Add(new List<int> { seg[1], -1 });
        }

        // При равных значениях точки с -1 идут первыми
        points.Sort((a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));

        int maxRooms = 0;
        int currRooms = 0;
        foreach (var point in points)
        {
            currRooms += point[1];
            maxRooms = Math.Max(maxRooms, currRooms);
        }
        return maxRooms;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

int countMeetingRooms(vector<vector<int>> segments) {
    vector<vector<int>> points;
    for (const auto& seg : segments) {
        // Точка начала отрезка, +1 - нужна ещё одна комната
        points.push_back({seg[0], +1});
        // Точка конца отрезка, -1 - комната освобождается
        points.push_back({seg[1], -1});
    }

    // При равных значениях точки с -1 идут первыми
    sort(points.begin(), points.end());

    int maxRooms = 0;
    int currRooms = 0;
    for (const auto& point : points) {
        currRooms += point[1];
        maxRooms = max(maxRooms, currRooms);
    }
    return maxRooms;
}

package main

func countMeetingRooms(segments [][]int) int {
    points := [][]int{}
    for _, seg := range segments {
        // Точка начала отрезка, +1 - нужна ещё одна комната
        points = append(points, []int{seg[0], +1})
        // Точка конца отрезка, -1 - комната освобождается
        points = append(points, []int{seg[1], -1})
    }

    // При равных значениях точки с -1 идут первыми
    sort.Slice(points, func(i, j int) bool {
        if points[i][0] == points[j][0] {
            return points[i][1] < points[j][1]
        }
        return points[i][0] < points[j][0]
    })

    maxRooms := 0
    currRooms := 0
    for _, point := range points {
        currRooms += point[1]
        if currRooms > maxRooms {
            maxRooms = currRooms
        }
    }
    return maxRooms
}

import java.util.*;

public class Solution {
    public static int countMeetingRooms(List<List<Integer>> segments) {
        List<List<Integer>> points = new ArrayList<>();
        for (List<Integer> seg : segments) {
            // Точка начала отрезка, +1 - нужна ещё одна комната
            points.add(Arrays.asList(seg.get(0), +1));
            // Точка конца отрезка, -1 - комната освобождается
            points.add(Arrays.asList(seg.get(1), -1));
        }

        // При равных значениях точки с -1 идут первыми
        points.sort((a, b) -> a.get(0).equals(b.get(0)) ? a.get(1).compareTo(b.get(1)) : a.get(0).compareTo(b.get(0)));

        int maxRooms = 0;
        int currRooms = 0;
        for (List<Integer> point : points) {
            currRooms += point.get(1);
            maxRooms = Math.max(maxRooms, currRooms);
        }
        return maxRooms;
    }
}

from typing import List

def count_meeting_rooms(segments: List[List[int]]) -> int:
    points = []
    for seg in segments:
        # Точка начала отрезка, +1 - нужна ещё одна комната
        points.append([seg[0], +1])
        # Точка конца отрезка, -1 - комната освобождается
        points.append([seg[1], -1])

    # При равных значениях точки с -1 идут первыми
    points.sort()

    max_rooms = 0
    curr_rooms = 0
    for point in points:
        curr_rooms += point[1]
        max_rooms = max(max_rooms, curr_rooms)
    return max_rooms

export function countMeetingRooms(segments) {
    let points = [];
    for (let seg of segments) {
        // Точка начала отрезка, +1 - нужна ещё одна комната
        points.push([seg[0], +1]);
        // Точка конца отрезка, -1 - комната освобождается
        points.push([seg[1], -1]);
    }

    // При равных значениях точки с -1 идут первыми
    points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);

    let maxRooms = 0;
    let currRooms = 0;
    for (let point of points) {
        currRooms += point[1];
        maxRooms = Math.max(maxRooms, currRooms);
    }
    return maxRooms;
}

Оценка сложности

Время: O(n*log(n)), где n – размер массива segments. Основная часть времени уходит на сортировку.
Память: O(n). Дополнительная память расходуется под массив точек и сортировку.

Метод точек

“Метод точек” предполагает, что мы превращаем каждый отрезок в набор точек начала и конца и затем работаем с ними в одном общем массиве, предварительно отсортировав.

Что дальше

Чем больше тренируешься, тем лучше усваивается материал, поэтому скорее переходи к практическим задачам. Удачи в решении!