Задачи
May 2, 2022
Задача. Когда была максимальная численность населения?!
Задача. Дан двумерный массив arr, где каждый элемент массива arr[i] = [birth_i, death_i] указывает год рождения и год смерти i-го человека.
Справка: Население года х — это число людей, живущих в течение этого года. i-й человек считается в населении года x, если x находится в диапазоне [birthi, deathi - 1]. Учтите, что человек не засчитывается в год, когда он умер.
Необходимо вернуть самый ранний год с максимальной численностью населения.
- arr: [[1992, 1998], [1999, 2009]]
Output: 1992 - arr: [[1950, 1961], [1960, 1971], [1970, 1981]]
Output: 1960
Пояснение: в 1960, в 1970 - население 2 человека, но мы выбираем самый ранний год.
Разбор
- Определим предельные значения минимального и максимального года, если они не даны в условии.
- Создадим вспомогательный массив year размера MaxYear. Далее читаем исходный массив и заполняем наш массив year следующим образом:
year[arr[i][0]] += 1;
year[arr[i][1]] -= 1;
То есть прибавляем соотв. год рождения и вычитаем соотв.год смерти i-го человека. - Далее проходим по нашему созданному вспомогательному массиву и находим максимальный год.