4.26华为OD机试真题 新系统 - 最大化游戏试玩资格分发 (Java/Py/C/C++/Js/Go)

最大化游戏试玩资格分发

2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

新研发了一台游戏设备可以面向用户接受试玩。现有n个试玩申请，每个试玩有开始时间和结束时间。作为协调员，为了能让更多人体验到游戏，你需要对试玩申请进行选择，使得：

1. 任意两个被选中的试玩时间不重叠。

2. 任意两个被选中的试玩时间允许连续，例如[2,3]和[3,4]认为是可以都被安排的。

3. 被安排的试玩数量最大化。

请问最多能安排多少场试玩？

输入描述

第一行：一个整数n(1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105)，表示试玩申请数量。

第二行：是一个长度为n的数组，数组的每个元素为两个整数start和end(0 ≤ s t a r t ≤ e n d ≤ 10 9 0 \le start \le end \le 10^90≤start≤end≤109)，表示试玩的开始和结束时间。数组每个元素以空格分割，元素内部中start和end使用逗号分割。

输出描述

一个整数，表示最多能安排的试玩数量。

示例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

说明

5个试玩申请时间都不重合，可同时满足

示例3

输入

1 1,5

输出

1

说明

只有一个试玩请求，可以直接安排。

示例4

输入

3 1,5 2,4 3,6

输出

1

说明

所有试玩时间相互都冲突，只能安排一场。

解题思路

本题是一个经典的区间调度问题（Activity Selection Problem），通常使用贪心算法求解。
目标是从给定的n nn个区间中，选出尽可能多的互不重叠的区间。

核心思想：
为了能够安排更多的试玩，我们需要优先安排那些结束时间早的试玩，这样能为后面的试玩留出更多的时间。
具体步骤如下：

1. 排序：将所有的试玩申请按照结束时间从小到大进行排序。如果结束时间相同，按开始时间排序也可。
2. 贪心选择：维护一个当前已安排试玩的结束时间current_end（初始值为 -1）。遍历排序后的申请：
   • 如果当前试玩的开始时间≥ \ge≥current_end，说明它与之前安排的试玩不冲突（题目允许连续时间，例如[2,3]和[3,4]可以同时安排）。
   • 选择该试玩，将安排的数量加一，并更新current_end为当前试玩的结束时间。
3. 返回结果：遍历结束后，所选择的试玩数量即为最大能安排的场次。

复杂度分析：

• 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，主要耗时在对所有区间进行排序。贪心遍历只需要O ( n ) O(n)O(n)。
• 空间复杂度：O ( 1 ) O(1)O(1)或O ( n ) O(n)O(n)，取决于语言内部排序算法的空间开销。

Java

importjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);if(!sc.hasNextInt())return;intn=sc.nextInt();int[][]intervals=newint[n][2];for(inti=0;i<n;i++){String[]parts=sc.next().split(",");intervals[i][0]=Integer.parseInt(parts[0]);intervals[i][1]=Integer.parseInt(parts[1]);}// 按结束时间升序排序Arrays.sort(intervals,(a,b)->Integer.compare(a[1],b[1]));intcount=0;intcurrentEnd=-1;for(inti=0;i<n;i++){if(intervals[i][0]>=currentEnd){count++;currentEnd=intervals[i][1];}}System.out.println(count);}}

Python

importsysdefsolve():input=sys.stdin.read data=input().split()ifnotdata:returnn=int(data[0])intervals=[]foriinrange(1,n+1):s,e=map(int,data[i].split(','))intervals.append((s,e))# 按结束时间升序排序intervals.sort(key=lambdax:x[1])count=0current_end=-1fors,einintervals:ifs>=current_end:count+=1current_end=eprint(count)if__name__=='__main__':solve()

JavaScript

constfs=require('fs');functionmain(){constinput=fs.readFileSync('/dev/stdin','utf-8').trim().split(/\s+/);if(input.length<2)return;constn=parseInt(input[0]);constintervals=[];for(leti=1;i<=n;i++){constparts=input[i].split(',');intervals.push({start:parseInt(parts[0]),end:parseInt(parts[1])});}// 按结束时间升序排序intervals.sort((a,b)=>a.end-b.end);letcount=0;letcurrentEnd=-1;for(leti=0;i<n;i++){if(intervals[i].start>=currentEnd){count++;currentEnd=intervals[i].end;}}console.log(count);}main();

C++

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespacestd;structInterval{intstart;intend;};intmain(){intn;if(!(cin>>n))return0;vector<Interval>intervals(n);for(inti=0;i<n;i++){string s;cin>>s;size_t pos=s.find(',');intervals[i].start=stoi(s.substr(0,pos));intervals[i].end=stoi(s.substr(pos+1));}// 按结束时间升序排序sort(intervals.begin(),intervals.end(),[](constInterval&a,constInterval&b){returna.end<b.end;});intcount=0;intcurrentEnd=-1;for(inti=0;i<n;i++){if(intervals[i].start>=currentEnd){count++;currentEnd=intervals[i].end;}}cout<<count<<endl;return0;}

Go

packagemainimport("fmt""sort""strconv""strings")typeIntervalstruct{startintendint}funcmain(){varnint_,err:=fmt.Scan(&n)iferr!=nil{return}intervals:=make([]Interval,n)fori:=0;i<n;i++{varsstringfmt.Scan(&s)parts:=strings.Split(s,",")start,_:=strconv.Atoi(parts[0])end,_:=strconv.Atoi(parts[1])intervals[i]=Interval{start,end}}// 按结束时间升序排序sort.Slice(intervals,func(i,jint)bool{returnintervals[i].end<intervals[j].end})count:=0currentEnd:=-1fori:=0;i<n;i++{ifintervals[i].start>=currentEnd{count++currentEnd=intervals[i].end}}fmt.Println(count)}

C语言

#include<stdio.h>#include<stdlib.h>typedefstruct{intstart;intend;}Interval;intcompare(constvoid*a,constvoid*b){Interval*ia=(Interval*)a;Interval*ib=(Interval*)b;returnia->end-ib->end;}intmain(){intn;if(scanf("%d",&n)!=1)return0;Interval*intervals=(Interval*)malloc(n*sizeof(Interval));for(inti=0;i<n;i++){scanf("%d,%d",&intervals[i].start,&intervals[i].end);}// 按结束时间升序排序qsort(intervals,n,sizeof(Interval),compare);intcount=0;intcurrentEnd=-1;for(inti=0;i<n;i++){if(intervals[i].start>=currentEnd){count++;currentEnd=intervals[i].end;}}printf("%d\n",count);free(intervals);return0;}

完整用例

用例1

5 1,3 2,4 3,5 4,6 5,7

用例2

3 1,2 2,3 1,3

用例3

5 17,22 2,4 18,21 18,23 16,19

用例4

8 2,10 4,10 1,10 5,10 1,10 8,10 2,10 5,10

用例5

10 11,15 7,17 14,23 29,31 10,19 23,29 3,7 15,23 6,11 28,32

用例6

12 17,20 20,23 7,10 10,13 2,4 4,5 1,2 13,14 5,7 23,25 25,27 14,17

用例7

15 34,43 27,31 37,41 46,49 16,22 31,40 8,18 13,21 37,44 32,42 25,31 14,15 2,3 45,47 6,11

用例8

18 14,32 19,30 17,25 12,15 6,20 1,21 2,7 4,6 1,2 7,25 20,31 9,10 19,38 1,3 12,26 3,19 9,19 8,10

用例9

20 75,76 55,67 11,16 34,47 29,34 12,17 9,12 41,54 50,56 30,37 26,41 44,45 93,102 17,20 25,26 30,41 40,43 97,109 84,96 23,26

用例10

20 11,13 33,35 19,23 1,5 13,17 36,39 23,28 32,33 58,62 7,9 68,73 41,43 29,30 79,84 56,57 44,48 49,54 67,68 63,65 74,79