@DarkOracleLex

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

Задание:
Петя решил узнать, когда программисту выгоднее всего искать работу на hh.ru. Конечно, когда больше всего открыто вакансий.

Он выгрузил в текстовый файл время открытия и закрытия всех подходящих вакансий за 2019 год.

Теперь нужно определить период времени, когда открытых вакансий было больше всего.

Считаем, что:

- начальное и конечное время всегда присутствуют;
- начальное время всегда меньше или равно конечному;
- начальное и конечное время включены в интервал.

Входные данные
Входная информация поступает из стандартного ввода, в первой строке приходит 1 число - количество вакансий. Каждая из следующих строк содержит информацию о вакансии в виде двух чисел – начальное и конечное время, они разделены пробелом. Время задается в секундах (https://ru.wikipedia.org/wiki/Unix-время). Некорректные данные на вход не поступают, дополнительные проверки не требуются.

Выходные данные
В качестве ответа в стандартный вывод через пробел нужно вывести два числа: количество найденных интервалов и сумму длительности интервалов в секундах (начальная и конечная секунды должны быть включены в интервал).

Пример 1
Входные данные:

1
1595862781 1595862785
Выходные данные: 1 5

Пример 2
Входные данные:

2
1595862781 1595862783
1595862782 1595862784
Выходные данные: 1 2

Пример 3
Входные данные:

2
1595862781 1595862782
1595862783 1595862784
Выходные данные: 2 4

Примечания по оформлению решения
При отправке решений на Java необходимо назвать исполняемый класс Main. В решении не нужно указывать пакет.

Для работы со стандартным потоком ввода в JS используйте require('readline'), а для работы со стандартным потоком вывода - console.log(String(data)).

Пример ввода-вывода на JS:
const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
rl.on('line', (line) => {
    // Введенная строка в переменной line, тут можно написать решение
    console.log(String(result));
    rl.close();
    return;
}).on('close', () => process.exit(0));

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

Моё решение (данные тесты проходит, но выдаёт ошибку в закрытых внутренних тестах):
const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
let lines = [];
rl.on('line', (line) => {
  lines.push(line);
}).on('close', () => {
  function calculateTime(strArr) {
    let vacanciesNum = strArr.shift();
    let vacanciesTime = strArr;
    let intervalFound = [];
    let count = 0;
    vacanciesTime.sort();

    vacanciesTime.reduce((prev, next) => {
      if (prev === next) {
        count++;
      }
    });

    for (let i = 0; i < vacanciesNum; i++) {
      let startTime = +vacanciesTime[i].split(" ")[0];
      let endTime = +vacanciesTime[i].split(" ")[1];
      let intervalFoundI = [];

      for (let j = 0; j < vacanciesNum; j++) {
        if (
          startTime <= +vacanciesTime[j].split(" ")[1] &&
          endTime >= +vacanciesTime[j].split(" ")[0]
        ) {
          intervalFoundI.push(vacanciesTime[j]);
        } // a.start <= b.end AND a.end >= b.start
      }
      intervalFound.push(intervalFoundI);
    } // находим все вхождения интервалов

    intervalFound = intervalFound.filter(
      ((r = {}), (a) => !(r[a] = ++r[a] | 0))
    ); // убираем одинаковые вхождения

    let maxLength = intervalFound.reduce(function (acc, el) {
      return el.length > acc ? el.length : acc;
    }, 0); // считаем максимальную длину массива

    intervalFound = intervalFound.filter((val) => {
      return val.length === maxLength;
    }); // отфильтровываем только максимальные значения

    let totalIntervalLength = intervalFound.reduce(
      (acc, val) => {
        let maxStart = val[0].split(" ")[0];
        let minEnd = val[0].split(" ")[1];

        for (const str of val) {
          if (maxStart < str.split(" ")[0]) {
            maxStart = str.split(" ")[0];
          }
          if (minEnd > str.split(" ")[1]) {
            minEnd = str.split(" ")[1];
          }
        }

        return (acc += minEnd - maxStart + 1);
      },
      0
    ); // Вычисляем общую длину интервала

    return `${
      count + intervalFound.length
    } ${totalIntervalLength}`;
  }
  
  console.log(calculateTime(lines));
  process.exit(0);
});
  • Вопрос задан
  • 279 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Мне лень разбираться в вашем коде. Вот правильное решение:

Для всех интервалов добавить в массив точек пары {время начала, +1} и {время конца+1, -1}. Это массив точек - границ вакансий на оси времени (прибавляем 1 к времени конца, потому что последняя секунда включена в интервал). Потом сортируем этот массив. Теперь одиним проходом можно выделить из массива все отрезки времени и сколько на них было открыто вакансий.

Для этого заведите счетчик, изначально равный нулю и пройдитесь по массиву прибавляя текущее второе значение в парек счетчику в конце цикла.
Перед этим, если текущая точка лежит правее предыдущей, то отрезок от предыдущей точки до текущей имеет ровно столько открытых вакансий, сколько записано в счетчике.

Для простоты советую сначла одним циклом выделить все отрезки и сложить их в отдельный массив (опять пара - длина отрезка, количество вакансий). Потом пройтись по массиву (или во время складывания) найти максимальное количество вакансий. Потом пройтись еще раз и просуммировать времена для всех отрезков с данным количеством вакансий.

Еще можете посмотреть предыдущий ответ вашему товарищу по курсу: В чем ошибка в алгоритме поиска количества интервалов?
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы