|
第二题:
google: Find the point where maximum intervals overlap
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
max_overlapping(vector<pair<int, int>> &ranges)
{
int n = (int)ranges.size();. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
vector<int> start, end;
for (auto p: ranges) {
start.push_back(p.first);
end.push_back(p.second);
}
sort(start.begin(), start.end());
sort(end.begin(), end.end());
int count = 0, max_count = 0;
int i = 0, j = 0;
int result = start[0];
while (i < n && j < n) {
if (start < end[j]) {
i++;
if (++count > max_count) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
max_count = count;
result = start;
}
} else {
j++;
count--;. Waral 鍗氬鏈夋洿澶氭枃绔,
}
}
return result;
}
int main(). From 1point 3acres bbs
{
vector<pair<int,int>> ranges;
ranges.push_back(make_pair(-1,2));
ranges.push_back(make_pair(0,0));
ranges.push_back(make_pair(1,1));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
cout << max_overlapping(ranges) << endl;
return 0;
}[/code] |
|