[hihoCoder] 任务分配 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
Read full article from [hihoCoder] 任务分配 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
给定 N 项任务的起至时间( S1, E1 ), ( S2, E2 ), ..., ( SN, EN )， 计算最少需要多少台机器才能按时完成所有任务。
同一时间一台机器上最多进行一项任务，并且一项任务必须从头到尾保持在一台机器上进行。任务切换不需要时间。
输入
第一行一个整数 N，(1 ≤ N ≤ 100000)，表示任务的数目。 以下 N 行每行两个整数 Si, Ei，(0 ≤ Si < Ei ≤ 1000000000)，表示任务的起至时间。
输出
输出一个整数，表示最少的机器数目。
样例输入
5
1 10
2 7
6 9
3 4
7 10
样例输出
3
思路: 要计算最大重叠区间的, 我们可以先以起始位置排序. 然后遍历数组, 每次将终点加入到二叉排序树set中, 如果当前的起点比set中的某个终点大, 就从set中将那个终点删除掉, 这样set最大的长度即是最大的重叠区间数目.
int main()
{
int N, start, end, Max = 0;
vector<pair<int, int> > time;
multiset<int> st;
cin>>N;
for(int i = 0; i < N; i++)
{
cin >> start >> end;
time.push_back(make_pair(start, end));
}
sort(time.begin(), time.end());
for(int i = 0; i< (int)time.size(); i++)
{
set<int>::iterator it = st.begin();
while(it != st.end())
{
if(time[i].first >= *it) it = st.erase(it);
else break;
}
st.insert(time[i].second);
Max = max(Max, (int)st.size());
}
cout << Max << endl;
return 0;
}
Read full article from [hihoCoder] 任务分配 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
