題目連結:
題目意譯:
你被給定一個二維整數陣列 logs,其中 logs[i] = [birthi, deathi] 代表第 i 個人的出生以及死亡年份。
年份 x 的人口數為該年活著的人之個數。如果 x 位於範圍 [birthi, deathi - 1] 之內(含端點)則第 i 個人將會被算進人口數中。注意到在某人死亡年份,他們是不算在該年人口數中的。
回傳最早有著最大人口數的年份。
限制:
1 ≦ logs.length ≦ 100
1950 ≦ birthi < deathi ≦ 2050
範例測資:
範例 1:
輸入: logs = [[1993,1999],[2000,2010]]
輸出: 1993
解釋: 最大人口數為 1,而且 1993 是最早有著這個人口數的。
範例 2:
輸入: logs = [[1950,1961],[1960,1971],[1970,1981]]
輸出: 1960
解釋:
最大人口數為 2,而且其發生於 1960 和 1970。
它們之中最早的年份為 1960。
解題思維:
可以看到年份的跨度才足足 101 年而已,而且 logs 的長度最大也僅僅只有 100。
因此我們可以直接窮舉所有年份(即從 1950 年開始),然後對每個年份去看這個年份落於 logs 中多少人的生死年份之間。然後取其中的最大值之發生年份,即可得到所求(如題目所述,多個最大人口數之年份則取最早的)。
如果題目的年份跨度變大了,而且 logs 的最大長度也變長的話,就需要類似
這題的解法(即掃描線演算法(Sweep Line Algorithm))。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。