Living People: Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive. You may assume that all people were born between 1900 and 2000 (inclusive). If a person was alive during any portion of that year, they should be included in that year’s count. For example, Person (birth= 1908, death= 1909) is included in the counts for both 1908 and 1909.
Hints: #476, #490, #507, #514, #523, #532, #541, #549, #576
1
2
3
4
5
6
7
|
public class Person {
private int final birthYear;
private int final deathYear;
// getters
}
List<Human> people = ...;
|
解法
维护一个delta数组代表1900年到2001年，遇到出生的就在slot上+1，遇到死亡的就在slot上-1，然后将其做成累加数列，结果就变成了每年还有多少人活着的数列。最后遍历这个数组找到最大值所在的slot，知道其年份。
1
2
3
4
5
6
7
8
9
10
11
|
b=1904, d=1920
b=1910, d=1918
index: 0 1 2 3 4 ... 10 ... 18 19 20 21
delta: 0 0 0 0 1 1 0 -1 0 -1
变成累加数列:
index: 0 1 2 3 4 ... 10 ... 18 19 20 21
livin: 0 0 0 0 1 2 2 1 1 0
当你求1919年多少人活着，那就是1人
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
private int static final int START = 1900;
private int[] living = new int[2000 - START + 2];
public void process(List<Person> people) {
for (Person person: people) {
living[person.birthYear - START]++;
// 死亡计数延后一年，根据题意1980年死的人在1980年还活着
living[person.deathYear - START + 1]--;
}
// 计算每年活着的人数
for (int i = 1; i < living.length; i++) {
living[i] += living[i - 1];
}
}
public int maxLivingYear() {
int maxLinvingYear = 0;
int maxLiving = 0;
for (int i = 0; i < living.length; i++) {
if (living[i] > maxLiving) {
maxLiving = living[i];
maxLinvingYear = i + START;
}
}
return maxLinvingYear;
}
|
评论