Алгоритмы и структуры данных

2.3. Демонстрация - Разбор задачи валидации скобочных выражений

Шаг 1

На примере этой задачи можно понять, насколько правильный подход к подготовке данных для задачи имеет вес в производительности и простоте решения. Офис X работает по правилам коворкинга: каждый сотрудник может работать из дома или приходить в офис. В спокойные дни в офисе тихо, приходят пара-тройка людей. А ближе к релизам/отчетным периодам/другим завалам людей гораздо больше, но все сотрудники всё равно никогда не выходят. Начальство хочет какое-то время понаблюдать, сколько же человек максимум приходят в офис, чтобы сократить количество «посадочных мест» и меньше платить за аренду. Для этого они наладили систему, которая фиксирует время захода и выхода людей из офиса, и планируют из этих данных получить максимальное количество присутствующих сотрудников в день. Система эта сохраняет нужные данные в формате [времяВхода, времяВыхода] для каждого сотрудника. Если люди входят и выходят одновременно, считается, что выход происходит раньше (уходящий человек уже встал с места и освободил его, а входящий ещё не успел занять). Ваша задача — написать функцию, получающую из информации в системе максимальное количество одновременно находящихся сотрудников в офисе. Если вы ещё не решали эту задачу, остановитесь и попробуйте сами.


import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function count(input) {
  return 0;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 2

Если оперировать таким набором данных, то решения будут довольно сложными как алгоритмически, так и в целом для понимания. Например, можно создать объект, в котором ключи будут конкретным моментом времени, а значения — количеством людей в этот момент. Заполнять этот объект довольно просто: будем брать каждый интервал и в цикле от его начала до его конца станем прибавлять 1 к каждому моменту времени, а потом просто найдём ключ с максимальным значением. Но! Если время хранится в миллисекундах, как это чаще всего и делается, то на 12 часов открытого офиса будет приходиться 43200000 ключей! Расходы памяти просто огромнейшие, да и по времени заполнения это решение очень медленное.


import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function count(input) {
  const logs = {};

  for (const [startTime, endTime] of input) {
    for (let i = startTime; i < endTime; i++) {
      logs[i] = logs[i] ? logs[i] + 1 : 1;
    }
  }

  return Math.max(...Object.values(logs), 0);
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 3

А если взглянуть на эту задачу под немного другим углом? Например, условный охранник, который хочет потягаться с новой системой учёта, решал бы эту задачу совершенно другим образом. По мере пропуска людей через турникеты на входе можно просто вести учёт людей, находящихся в офисе в каждый конкретный момент времени. Если человек заходит, прибавляем к текущему числу единицу, выходит — отнимаем. Охраннику всё равно, входил в этот момент Паша, Игорь или Женя. Ему важно, что кто-то когда-то вошёл, а кто-то когда-то вышел. Он не связывает эти события в пары, как это делает система. Тогда и максимум можно обновлять по мере продвижения людей: если вошло больше людей, чем было до этого, обновляем, если нет — не трогаем.


import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function count(input) {
  return 0;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 4

Если перекладывать это решение в код, то для начала нам нужно преобразовать данные в такой формат событий «прохода через турникеты». Например, возьмём следующую структуру объекта:

{
  time: 0,
  isEntering: true, // если в этот момент человек входил — true, выходил — false
}

И перегоним наблюдения системы в него. Это займет у нас O(n) времени.

import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function count(input) {
  const entries = [];

  for (const [enteringTime, leavingTime] of input) {
    entries.push({
      time: enteringTime,
      isEntering: true,
    });

    entries.push({
      time: leavingTime,
      isEntering: false,
    })
  }

  return 0;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 5

Так как данные в системе у нас никак не сортированы по времени, отсортируем их. Сортировка, как мы помним (но пока не понимаем), заняла у нас O(nlogn).


import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function compareEntries(left, right) {
  // Выход раньше входа в то же время
  if (left.time === right.time) {
    return left.isEntering ? 1 : -1;
  }

  return left.time - right.time;
}

function count(input) {
  const entries = [];

  for (const [enteringTime, leavingTime] of input) {
    entries.push({
      time: enteringTime,
      isEntering: true,
    });

    entries.push({
      time: leavingTime,
      isEntering: false,
    })
  }

  entries.sort(compareEntries);

  return 0;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 6

Теперь просто пройдёмся «глазами охранника» по этому массиву и посчитаем максимальное количество людей. И это тоже заняло у нас O(n) времени. Попробуйте посчитать общую сложность алгоритма сами. Если у вас получилось O(nlogn), то вы абсолютно правы! Если нет — ничего страшного, просто повторите правила оценивания алгоритмов из первого раздела.


import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function compareEntries(left, right) {
  // Выход раньше входа в то же время
  if (left.time === right.time) {
    return left.isEntering ? 1 : -1;
  }

  return left.time - right.time;
}

function count(input) {
  const entries = [];

  for (const [enteringTime, leavingTime] of input) {
    entries.push({
      time: enteringTime,
      isEntering: true,
    });

    entries.push({
      time: leavingTime,
      isEntering: false,
    })
  }

  entries.sort(compareEntries);

  let currentCount = 0;
  let maximumCount = 0;

  for (const {isEntering} of entries) {
    currentCount += isEntering ? 1 : -1;

    maximumCount = Math.max(currentCount, maximumCount);
  }

  return maximumCount;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

Шаг 7

Эта задача очень хорошо показывает, что правильно выбранная структура для хранения данных — ключ к простому решению задачи. Если у вас возникают трудности при решении той или иной рабочей задачи — попробуйте взглянуть на неё с другой стороны. Возможно, данные в том формате, в котором они даны, не совсем подходят для какой-то конкретной задачи. Попробуйте абстрагироваться от них и подумать, какое представление данных позволило бы прийти к решению максимально просто.


 import {test} from "./tester.js"

/*
Примеры:
count([]) // 0
count([[1, 5], [5, 10]]) // 1
count([[1, 5], [0, 1], [4, 5]]) // 2
count([[1, 10], [5, 6], [2, 3], [7, 8]]) // 2
count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]) // 4
*/

function compareEntries(left, right) {
  // Выход раньше входа в то же время
  if (left.time === right.time) {
    return left.isEntering ? 1 : -1;
  }

  return left.time - right.time;
}

function count(input) {
  const entries = [];

  for (const [enteringTime, leavingTime] of input) {
    entries.push({
      time: enteringTime,
      isEntering: true,
    });

    entries.push({
      time: leavingTime,
      isEntering: false,
    })
  }

  entries.sort(compareEntries);

  let currentCount = 0;
  let maximumCount = 0;

  for (const {isEntering} of entries) {
    currentCount += isEntering ? 1 : -1;

    maximumCount = Math.max(currentCount, maximumCount);
  }

  return maximumCount;
}

test(count([]), 0)
test(count([[1, 5], [5, 10]]), 1)
test(count([[1, 5], [0, 1], [4, 5]]), 2)
test(count([[1, 10], [5, 6], [2, 3], [7, 8]]), 2)
test(count([[1, 2], [1, 10], [4, 9], [8, 15], [5, 6], [8, 16]]), 4)

File tester.js


const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}