生存人数

给定 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]
通过次数6,168提交次数8,986

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/living-people-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        if (birth == null || death == null) return 0;

        Arrays.sort(birth);
        Arrays.sort(death);

        int[] arr = new int[birth.length];

        arr[0] = 1;
        for (int i = 1; i < birth.length; i++) {
            arr[i] = arr[i - 1] + 1;
        }

        int maxIndex = 0, maxVal = 0;

        for (int i = 0; i < death.length; i++) {
            int j = 0;
            while (j < death.length && birth[i] > death[j]) {
                arr[i]--;
                j++;
            }
            if (arr[i] > maxVal) {
                maxIndex = i;
                maxVal = arr[i];
            }
        }

        return birth[maxIndex];
    }
}

前缀和

class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
		int[] lives = new int[102];
		for (int birthyear : birth)
			lives[birthyear - 1900]++;
		for (int deathyear : death)
			lives[deathyear - 1900 + 1]--;

		int[] preSum = new int[102];
		preSum[0] = lives[0];
		for (int i = 1; i < preSum.length; i++) {
			preSum[i] = lives[i] + preSum[i - 1];
		}

		int maxlives = -1;
		int minyear = 0;
		for (int i = 0; i < preSum.length; i++) {
			if (preSum[i] > maxlives) {
				minyear = i + 1900;
				maxlives = preSum[i];
			}
		}
		return minyear;
	}
}

作者：cjvv
链接：https://leetcode-cn.com/problems/living-people-lcci/solution/javaqian-zhui-he-by-cjvv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        int[] changes = new int[102];
        int len = birth.length, res = 1900, max_alive = 0, cur_alive = 0;
        for (int i = 0; i < len; ++i) {
            ++changes[birth[i] - 1900];
            --changes[death[i] - 1899];
        }
        for (int i = 1; i < 101; ++i) {
            cur_alive += changes[i];
            if (cur_alive > max_alive) {
                max_alive = cur_alive;
                res = 1900 + i;
            }
        }
        return res;
    }
}
作者：gfu
链接：https://leetcode-cn.com/problems/living-people-lcci/solution/shu-zu-cun-chu-mei-nian-ren-shu-bian-hua-by-gfu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信