活动调度

╰半橙微兮° 2022-05-27 21:00 18阅读 0赞

## 活动调度 ##

输入要求：

第一行为活动的个数 N(1<=N<=1 000 000) 。

接下来 N 行为 Si 和 Fi(0<=Si<Fi<=2 000 000 000) ，分别代表第 i 个活动的开始时间和结束时间。活动 i 的区间段为 \[Si,Fi)

输出要求：

输出有一行 M ，为所需教室的最小数量。

<table style="max-width:100%;border-spacing:0px;width:1650px;margin-bottom:20px;background-color:transparent;"> 
 <thead> 
  <tr> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">&nbsp;</th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">测试用例 1</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71142&amp;test=90949&amp;type=in&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">11↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">1&nbsp;4↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">3&nbsp;5↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">0&nbsp;6↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">5&nbsp;7↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">3&nbsp;8↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">5&nbsp;9↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">6&nbsp;10↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">8&nbsp;11↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">8&nbsp;12↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">2&nbsp;13↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">12&nbsp;14↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71142&amp;test=90949&amp;type=out&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">5↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">2秒</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">64M</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">0</td> 
  </tr> 
 </tbody> 
</table>

![70][]

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    #define Maxn 1000005
    
    int s[Maxn];
    int f[Maxn];
    int N;
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> N;
    	for (int i = 0; i < N; i++)
    		cin >> s[i] >> f[i];
    	sort(s, s + N);
    	sort(f, f + N);
    	int ans = 0;
    	int cnt = 0;
    	int i=0, j=0;
    
    	while (i < N&&j < N)//类似于归并排序
    	{
    		if (s[i] < f[j])//遇到左
    		{
    			cnt++;
    			i++;
    			ans = max(ans, cnt);
    		}
    		else if (s[i]>f[j])//遇到右
    		{
    			cnt--;
    			j++;
    		}
    		else//遇到左右两数相等
    		{
    			cnt--;
    			j++;
    			cnt++;
    			i++;
    			ans = max(ans, cnt);
    			
    		}
    	}
    	cout << ans<<endl;
    	return 0;
    }

[70]: /images/20220528/ccacc4b5dbb94e929f0464de1ba463b9.png