题解：瑞学堂 瑞瑞的会议安排

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

瑞学堂：瑞瑞的会议安排

【题目描述】

瑞瑞是一家科技公司的CEO，每天都要参加许多场会议。今天有n nn场会议，第i ii场会议的开始时间为s i s_isi​，结束时间为e i e_iei​。

由于时间冲突，瑞瑞不可能参加所有的会议。他决定在一天中参加两段不相交的时间段，中间可以有一段休息时间。具体地，他可以选择两个时间段[ L 1 , R 1 ] [L_1,R_1][L1​,R1​]和[ L 2 , R 2 ] [L_2,R_2][L2​,R2​]，其中R 1 < L 2 R_1<L_2R1​<L2​，然后在第一个时间段内参加若干场会议（这些会议的开始时间和结束时间必须全部包含在[ L 1 , R 1 ] [L_1,R_1][L1​,R1​]内），在第二个时间段内同样参加若干场会议（全部包含在[ L 2 , R 2 ] [L_2,R_2][L2​,R2​]内），并且要求他参加的会议总数最多。

注意：

• 一场会议不能跨时间段参加。
• 在同一个时间段内，瑞瑞不能同时参加多场会议，即所选会议的时间（左闭右闭区间）不能有重叠。
• 会议的时间区间是左闭右闭区间[ s i , e i ] [s_i,e_i][si​,ei​]。
• 每个时间段内参加的会议数量可以为0 00。

请你帮助瑞瑞算出他最多能参加多少场会议。

【输入】

第一行一个整数n nn，表示会议的数量。

接下来n nn行，每行两个整数s i , e i s_i,e_isi​,ei​，表示第i ii场会议的开始和结束时间。

【输出】

输出一个整数，表示瑞瑞最多能参加的会议数量。

【输入样例】

4 1 3 2 4 5 7 6 8

【输出样例】

2

【核心思想】

1. 问题分析：给定n nn场会议（时间区间[ s i , e i ] [s_i, e_i][si​,ei​]），瑞瑞可以参加两段不相交的时间段，每段内部不能同时参加重叠会议，求最多能参加的会议总数。这是一个双段区间调度问题，关键在于将会议按结束时间排序后，枚举两段的分界点，分别计算前缀和后缀的最大不重叠会议数。

2. 算法选择：

   • 贪心排序：按结束时间升序排序，这是经典区间调度问题的最优策略（优先选结束早的会议，留下更多时间给后续会议）
   • 前缀/后缀预处理：计算p r e [ i ] pre[i]pre[i]（前i ii场会议中最多能选的不重叠会议数）和s u f [ i ] suf[i]suf[i]（后i ii场会议中最多能选的不重叠会议数）
   • 枚举分界点：枚举第一段结束于第i ii场会议，第二段从第i + 1 i+1i+1场开始，答案为max ⁡ ( p r e [ i ] + s u f [ i + 1 ] ) \max(pre[i] + suf[i+1])max(pre[i]+suf[i+1])

3. 关键步骤：

   • 读入与排序：读入n nn和会议数组a [ 1.. n ] a[1..n]a[1..n]，按结束时间r rr升序排序
   • 预处理前缀p r e [ i ] pre[i]pre[i]：p r e [ i ] pre[i]pre[i]表示前i ii场会议中最多能选的不重叠会议数
     • 贪心遍历：维护last（上一个已选会议的结束时间），若a [ i ] . l > l a s t a[i].l > lasta[i].l>last则选中，pre[i] = pre[i-1] + 1，更新last = a[i].r；否则pre[i] = pre[i-1]
   • 预处理后缀s u f [ i ] suf[i]suf[i]：s u f [ i ] suf[i]suf[i]表示从第i ii场到第n nn场中最多能选的不重叠会议数
     • 逆序贪心遍历：维护first（下一个已选会议的开始时间），若a [ i ] . r < f i r s t a[i].r < firsta[i].r<first则选中，suf[i] = suf[i+1] + 1，更新first = a[i].l；否则suf[i] = suf[i+1]
   • 枚举两段分界：a n s = max ⁡ i = 0 n ( p r e [ i ] + s u f [ i + 1 ] ) ans = \max_{i=0}^{n}(pre[i] + suf[i+1])ans=maxi=0n​(pre[i]+suf[i+1])（p r e [ 0 ] = 0 , s u f [ n + 1 ] = 0 pre[0] = 0, suf[n+1] = 0pre[0]=0,suf[n+1]=0）
   • 输出a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，排序O ( n log ⁡ n ) O(n \log n)O(nlogn)，预处理O ( n ) O(n)O(n)，枚举O ( n ) O(n)O(n)
   • 空间复杂度：O ( n ) O(n)O(n)，存储p r e prepre和s u f sufsuf数组

5. 双段贪心调度的核心思想：

   • 排序创造贪心最优性：按结束时间排序后，经典区间调度问题的贪心策略（选结束最早的兼容会议）可得到最优解
   • 前缀/后缀分解：将"两段不相交"的约束转化为"在某处切分，左边一段最优 + 右边一段最优"，避免直接处理两段交叉的复杂状态
   • 贪心最优子结构：前缀和后缀各自独立使用贪心策略，由于排序后的全局最优性，分解后的局部最优之和即为全局最优
   • 两段可为空的处理：p r e [ 0 ] = 0 pre[0] = 0pre[0]=0和s u f [ n + 1 ] = 0 suf[n+1] = 0suf[n+1]=0自然覆盖只选一段或一段都不选的情况
   • 适用于"将资源分为两段使用，每段内部有独立约束"的调度问题，核心在于排序后利用贪心最优性进行前后缀分解

【算法标签】

#贪心

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=2005;// 定义数组最大容量为2005structNode{intl,r;// l为会议开始时间，r为会议结束时间}a[N];// a数组存储n场会议的信息intn,ans;// n为会议数量，ans记录最多能参加的会议数// 自定义排序规则：按会议结束时间升序排列（贪心策略：优先选结束早的会议）boolcmp(Node x,Node y){returnx.r<y.r;// 按结束时间从小到大排序}intmain(){cin>>n;// 读入会议数量for(inti=1;i<=n;i++)// 读入每场会议的开始和结束时间cin>>a[i].l>>a[i].r;sort(a+1,a+n+1,cmp);// 按结束时间升序排序所有会议// 贪心选择第一个时间段内的会议（经典区间调度问题）intlast=a[1].r;// last记录上一个已选会议的结束时间ans=1;// 第一个会议一定选for(inti=2;i<=n;i++)// 从第2个会议开始遍历{if(a[i].l<=last)// 如果当前会议开始时间小于等于上一个会议结束时间（有重叠）continue;// 不能参加，跳过ans++;// 可以参加，会议数加1last=a[i].r;// 更新last为当前会议的结束时间}cout<<ans<<endl;// 输出最多能参加的会议数量（注意：此代码只处理了单个时间段，未处理两个时间段的情况）return0;}

【运行结果】

4 1 3 2 4 5 7 6 8 2