面试题 16.10. 生存人数

Difficulty: **给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。 如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。 示例： 输入： birth = {1900, 1901, 1950} death = {1948, 1951, 2000} 输出： 1901 提示： 0 < birth.length == death.length <= 10000 birth[i] <= death[i] **

给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。

示例：

1
2
3
4

输入：
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
输出： 1901

提示：

  • 0 < birth.length == death.length <= 10000
  • birth[i] <= death[i]

Solution

Language: ****

 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
28
29
30
31
32
33
34
35
36
37

type Tree []int

func lowbit(u int) int {
	return int(u & -u)
}
func (cur Tree) Add(u, c int) {
	for ; u < len(cur); u++ {
		cur[u] += c
	}

}

func (cur Tree) Query(u int) int {
	var ans int
	for ; u > 0; u -= lowbit(u) {
		ans += cur[u]
	}
	return ans

}

func maxAliveYear(birth []int, death []int) int {
	var s  = make(Tree, 2000-1900+10)
	for i := 0; i < len(birth); i++ {
		s.Add(birth[i]-1900, 1)
		s.Add(death[i]-1899, -1)
	}
	var maxUserCnt, year int
	for i := 0; i < len(s); i++ {
		if maxUserCnt < s[i] {
			maxUserCnt = s[i]
			year = i + 1900
		}
	}
	return year

}