2026华为OD面试题021：最大化游戏试玩资格分发

题目描述新研发了一台游戏设备面向用户开放试玩。现在收到n个试玩申请每个申请有开始时间和结束时间。你是协调员要从这些申请里挑出一批满足任意两场被选中的试玩时间不重叠。允许连续衔接比如[2,3]和[3,4]可以同时安排。被安排的试玩数量要尽量多。问最多能安排多少场输入描述第一行整数n1 n 10^5表示申请数量。第二行n个元素每个元素是start,end元素之间用空格分隔start和end之间用逗号分隔0 start end 10^9。输出描述一个整数表示最多能安排的试玩数量。示例 1输入3 1,5 2,3 4,6输出2说明选[2,3]和[4,6]共 2 场。示例 2输入5 1,2 3,4 5,6 7,8 9,10输出5讲个故事游戏展的爆款试玩台小张在游戏展负责一台爆款试玩机。开展前收到一堆试玩申请每个玩家都报了一个想玩的时间段比如2 点到 3 点“4 点到 6 点”。机器就一台同一时间只能一个人玩。但前一个刚结束、下一个马上接上这没问题。小张的任务是从这堆申请里挑出一批时间上不打架数量越多越好。说白了这不就是活动安排问题吗核心原理为什么按结束时间排序这是经典的区间调度问题标准解法是贪心。贪心策略就一句话优先挑结束时间最早的那场。为啥这么选一场试玩结束得越早留给后面申请的时间窗口就越大后面能塞进去的场次就越多。每一步都给未来留余地总数自然最大。那能不能按开始时间排不行。举个反例三场申请[1,100]、[2,3]、[4,5]。按开始时间排先挑[1,100]后面两场全被它占掉只能安排 1 场。可按结束时间排挑[2,3]和[4,5]能安排 2 场。按区间长度挑最短的也不靠谱照样能造出反例。所以记住区间调度按结束时间排序从头往后扫能塞就塞。还有个细节。题目说允许连续[2,3]和[3,4]算不冲突。所以判断条件是下一场.start 上一场.end用不是差一个等号结果就错了。拿示例 1 验证一下三场[1,5]、[2,3]、[4,6]按结束时间排成[2,3]、[1,5]、[4,6]。先选[2,3]结束时间 3。[1,5]开始时间 1 小于 3跳过。[4,6]开始时间 4 大于等于 3选上。一共 2 场和答案对上。怎么实现读入n和n个区间。按结束时间升序排序结束时间相同的按开始时间排。第一场必选记下它的结束时间。从第二场开始扫如果当前场的开始时间上一场结束时间就选它更新结束时间。统计选中的场数输出。时间最大到10^9C/C 用long long存更稳避免溢出踩坑。说明原题文件在解题思路处截断只写到优先选择结束时间最早这里按常见的区间调度题型补全思路和代码。代码实现C 语言#includestdio.h#includestdlib.htypedefstruct{longlongs,e;}Seg;intcmp(constvoid*a,constvoid*b){Seg*x(Seg*)a,*y(Seg*)b;if(x-e!y-e)returnx-ey-e?-1:1;returnx-sy-s?-1:1;}intmain(){intn;if(scanf(%d,n)!1)return0;Seg*a(Seg*)malloc(n*sizeof(Seg));for(inti0;in;i){scanf(%lld,%lld,a[i].s,a[i].e);}qsort(a,n,sizeof(Seg),cmp);intcnt1;longlonglastEnda[0].e;for(inti1;in;i){if(a[i].slastEnd){cnt;lastEnda[i].e;}}printf(%d\n,cnt);free(a);return0;}C#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorpairlonglong,longlonga(n);for(inti0;in;i){charc;cina[i].firstca[i].second;}sort(a.begin(),a.end(),[](constautox,constautoy){if(x.second!y.second)returnx.secondy.second;returnx.firsty.first;});intcnt1;longlonglastEnda[0].second;for(inti1;in;i){if(a[i].firstlastEnd){cnt;lastEnda[i].second;}}coutcntendl;return0;}Javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnInteger.parseInt(sc.nextLine().trim());String[]partssc.nextLine().trim().split(\\s);long[][]anewlong[n][2];for(inti0;in;i){String[]pparts[i].split(,);a[i][0]Long.parseLong(p[0]);a[i][1]Long.parseLong(p[1]);}Arrays.sort(a,(x,y)-{if(x[1]!y[1])returnLong.compare(x[1],y[1]);returnLong.compare(x[0],y[0]);});intcnt1;longlastEnda[0][1];for(inti1;in;i){if(a[i][0]lastEnd){cnt;lastEnda[i][1];}}System.out.println(cnt);}}JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin});letlines[];rl.on(line,(line)lines.push(line.trim()));rl.on(close,(){constnparseInt(lines[0]);constpartslines[1].split(/\s/).slice(0,n);constaparts.map(p{const[s,e]p.split(,).map(Number);return[s,e];});a.sort((x,y)x[1]-y[1]||x[0]-y[0]);letcnt1;letlastEnda[0][1];for(leti1;in;i){if(a[i][0]lastEnd){cnt;lastEnda[i][1];}}console.log(cnt);});Pythonnint(input())partsinput().split()a[tuple(map(int,p.split(,)))forpinparts[:n]]a.sort(keylambdax:(x[1],x[0]))cnt1last_enda[0][1]foriinrange(1,n):ifa[i][0]last_end:cnt1last_enda[i][1]print(cnt)复杂度分析排序O(n * log n)一次扫描O(n)总时间复杂度O(n * log n)空间复杂度O(n)存所有区间n到 10 万O(n log n)完全跑得动不用考虑额外优化。总结一下这道题是区间调度的教科书案例记住三句话区间求最大不重叠数量按结束时间排序。从前往后扫能塞就塞。判断不打架用因为允许连续衔接。下次看到安排“最多能选几个”时间不冲突这类词先往活动安排问题上靠。容易踩的坑有两个一是顺手按开始时间排序结果被一个超长区间坑掉二是判断重叠时漏了等号把[2,3]和[3,4]误判成冲突。这两个点盯住基本就稳了。‍♂️你做区间题时最容易在哪一步翻车欢迎在评论区聊聊。