Maximum Population Year
给一个log, 是[出生年, 死亡年], 求哪个年代人最多.
用扫描线做,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int maximumPopulation(vector<vector<int>>& logs) { vector<int> v(200); for(auto l : logs){ v[l[0] - 1950]++; v[l[1] - 1950]--; } int maxx = 0; int tmp = 0; int res = 0; for(int i = 0; i < 200; i++){ tmp += v[i]; if(tmp > maxx){ maxx = max(maxx, tmp); res = i + 1950; } } return res; } }; |