本文分享的必刷题目是从蓝桥云课、洛谷、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_1L_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【核心思想】问题分析给定n nn场会议时间区间[ s i , e i ] [s_i, e_i][si​,ei​]瑞瑞可以参加两段不相交的时间段每段内部不能同时参加重叠会议求最多能参加的会议总数。这是一个双段区间调度问题关键在于将会议按结束时间排序后枚举两段的分界点分别计算前缀和后缀的最大不重叠会议数。算法选择贪心排序按结束时间升序排序这是经典区间调度问题的最优策略优先选结束早的会议留下更多时间给后续会议前缀/后缀预处理计算p r e [ i ] pre[i]pre[i]前i ii场会议中最多能选的不重叠会议数和s u f [ i ] suf[i]suf[i]后i ii场会议中最多能选的不重叠会议数枚举分界点枚举第一段结束于第i ii场会议第二段从第i 1 i1i1场开始答案为max ⁡ ( p r e [ i ] s u f [ i 1 ] ) \max(pre[i] suf[i1])max(pre[i]suf[i1])关键步骤读入与排序读入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].llast则选中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].rfirst则选中suf[i] suf[i1] 1更新first a[i].l否则suf[i] suf[i1]枚举两段分界a n s max ⁡ i 0 n ( p r e [ i ] s u f [ i 1 ] ) ans \max_{i0}^{n}(pre[i] suf[i1])ansmaxi0n​(pre[i]suf[i1])p r e [ 0 ] 0 , s u f [ n 1 ] 0 pre[0] 0, suf[n1] 0pre[0]0,suf[n1]0输出a n s ansans时间/空间复杂度时间复杂度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数组双段贪心调度的核心思想排序创造贪心最优性按结束时间排序后经典区间调度问题的贪心策略选结束最早的兼容会议可得到最优解前缀/后缀分解将两段不相交的约束转化为在某处切分左边一段最优 右边一段最优避免直接处理两段交叉的复杂状态贪心最优子结构前缀和后缀各自独立使用贪心策略由于排序后的全局最优性分解后的局部最优之和即为全局最优两段可为空的处理p r e [ 0 ] 0 pre[0] 0pre[0]0和s u f [ n 1 ] 0 suf[n1] 0suf[n1]0自然覆盖只选一段或一段都不选的情况适用于将资源分为两段使用每段内部有独立约束的调度问题核心在于排序后利用贪心最优性进行前后缀分解【算法标签】#贪心【代码详解】#includebits/stdc.husingnamespacestd;constintN2005;// 定义数组最大容量为2005structNode{intl,r;// l为会议开始时间r为会议结束时间}a[N];// a数组存储n场会议的信息intn,ans;// n为会议数量ans记录最多能参加的会议数// 自定义排序规则按会议结束时间升序排列贪心策略优先选结束早的会议boolcmp(Node x,Node y){returnx.ry.r;// 按结束时间从小到大排序}intmain(){cinn;// 读入会议数量for(inti1;in;i)// 读入每场会议的开始和结束时间cina[i].la[i].r;sort(a1,an1,cmp);// 按结束时间升序排序所有会议// 贪心选择第一个时间段内的会议经典区间调度问题intlasta[1].r;// last记录上一个已选会议的结束时间ans1;// 第一个会议一定选for(inti2;in;i)// 从第2个会议开始遍历{if(a[i].llast)// 如果当前会议开始时间小于等于上一个会议结束时间有重叠continue;// 不能参加跳过ans;// 可以参加会议数加1lasta[i].r;// 更新last为当前会议的结束时间}coutansendl;// 输出最多能参加的会议数量注意此代码只处理了单个时间段未处理两个时间段的情况return0;}【运行结果】4 1 3 2 4 5 7 6 8 2