Задачи
May 2, 2022

Задача. Когда была максимальная численность населения?!

Задача. Дан двумерный массив arr, где каждый элемент массива arr[i] = [birth_i, death_i] указывает год рождения и год смерти i-го человека.

Справка: Население года х — это число людей, живущих в течение этого года. i-й человек считается в населении года x, если x находится в диапазоне [birthi, deathi - 1]. Учтите, что человек не засчитывается в год, когда он умер.

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

Примеры:

  1. arr: [[1992, 1998], [1999, 2009]]
    Output: 1992
  2. arr: [[1950, 1961], [1960, 1971], [1970, 1981]]
    Output: 1960
    Пояснение: в 1960, в 1970 - население 2 человека, но мы выбираем самый ранний год.

Разбор

  1. Определим предельные значения минимального и максимального года, если они не даны в условии.
  2. Создадим вспомогательный массив year размера MaxYear. Далее читаем исходный массив и заполняем наш массив year следующим образом:
    year[arr[i][0]] += 1;
    year[arr[i][1]] -= 1;
    То есть прибавляем соотв. год рождения и вычитаем соотв.год смерти i-го человека.
  3. Далее проходим по нашему созданному вспомогательному массиву и находим максимальный год.

Реализация

Test

https://dotnetfiddle.net/h3tSDz