最大化游戏试玩资格分发(C/C/Py/Java/Js/Go)华为OD机试真题 华为OD上机考试真题 4月26号 100分题型华为OD机试真题目录点击查看: 华为OD机试真题题库目录机考题库 算法考点详解题目描述新研发了一台游戏设备可以面向用户接受试玩。现有 n个试玩申请每个试玩有开始时间和结束时间。作为协调员为了能让更多人体验到游戏你需要对试玩申请进行选择使得任意两个被选中的试玩时间不重叠。任意两个被选中的试玩时间允许连续例如 [2,3] 和 [3,4] 认为是可以都被安排的。被安排的试玩数量最大化。请问最多能安排多少场试玩输入描述第一行一个整数 n(1≤n≤10^5)表示试玩申请数量。第二行是一个长度为 n 的数组数组的每个元素为两个整数 start和 end(0 ≤ start≤end≤10^9)表示试玩的开始和结束时间。数组每个元素以空格分割元素内部中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说明所有试玩时间相互都冲突只能安排一场。题解思路贪心经典的区间调度问题对于这类在若干个时间区间内求最多不重叠时间区间数量的题都可以采用以下思路处理。首先将时间区间按照结束时间进行升序排序。每次贪心选择结束时间较早的试玩。贪心原理基于上一轮试玩结束时间越早越能留给后续试玩更多时间/对于代码逻辑实现为:定义count表示可选择数量定义lastEnd表示上轮试玩的结束时间。遍历排序之后的试玩时间如果start lastEnd则说明可安排试玩更新count, lastEndend最终count的值就是最大可安排数量。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorstring split(const string str, const string delimiter) { vectorstring result; size_t start 0; size_t end str.find(delimiter); while (end ! string::npos) { result.push_back(str.substr(start, end - start)); start end delimiter.length(); end str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } int getMaxPlayTime(int n, vectorvectorint playerTimeRange) { // 自定义排序,按照结束时间从小到大排序 sort(playerTimeRange.begin(), playerTimeRange.end(), [](vectorint a, vectorint b) { return a[1] b[1]; }); int count 0; int lastEnd 0; for (int i 0; i n; i) { int currentStart playerTimeRange[i][0]; int currentEnd playerTimeRange[i][1]; if (lastEnd currentStart) { count; lastEnd currentEnd; } } return count; } int main() { int n; cin n; cin.ignore(); string input; getline(cin, input); vectorstring records split(input, ); vectorvectorint playerTimeRange(n); for (int i 0; i n; i) { vectorstring time split(records[i], ,); playerTimeRange[i] {stoi(time[0]), stoi(time[1])}; } int res getMaxPlayTime(n, playerTimeRange); cout res; return 0; }JAVAimport java.util.*; public class Main { // 贪心按结束时间排序选择最多不重叠区间 public static int getMaxPlayTime(int n, int[][] playerTimeRange) { // 按结束时间升序排序 Arrays.sort(playerTimeRange, (a, b) - a[1] - b[1]); int count 0; int lastEnd 0; for (int i 0; i n; i) { int currentStart playerTimeRange[i][0]; int currentEnd playerTimeRange[i][1]; if (lastEnd currentStart) { count; lastEnd currentEnd; } } return count; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); sc.nextLine(); // 吃掉换行 String input sc.nextLine(); String[] records input.split( ); int[][] playerTimeRange new int[n][2]; for (int i 0; i n; i) { String[] time records[i].split(,); playerTimeRange[i][0] Integer.parseInt(time[0]); playerTimeRange[i][1] Integer.parseInt(time[1]); } int res getMaxPlayTime(n, playerTimeRange); System.out.println(res); } }Pythonimportsys# 贪心按结束时间排序defgetMaxPlayTime(n,playerTimeRange):# 按结束时间排序playerTimeRange.sort(keylambdax:x[1])count0lastEnd0foriinrange(n):currentStartplayerTimeRange[i][0]currentEndplayerTimeRange[i][1]iflastEndcurrentStart:count1lastEndcurrentEndreturncount# 读取输入nint(sys.stdin.readline().strip())input_strsys.stdin.readline().strip()recordsinput_str.split( )playerTimeRange[]forrecinrecords:start,endmap(int,rec.split(,))playerTimeRange.append([start,end])resgetMaxPlayTime(n,playerTimeRange)print(res)JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,function(line){lines.push(line.trim());});rl.on(close,function(){letnparseInt(lines[0]);letrecordslines[1].split( );letplayerTimeRange[];for(leti0;in;i){let[start,end]records[i].split(,).map(Number);playerTimeRange.push([start,end]);}// 贪心按结束时间排序playerTimeRange.sort((a,b)a[1]-b[1]);letcount0;letlastEnd0;for(leti0;in;i){letcurrentStartplayerTimeRange[i][0];letcurrentEndplayerTimeRange[i][1];if(lastEndcurrentStart){count;lastEndcurrentEnd;}}console.log(count);});Gopackagemainimport(bufiofmtossortstrconvstrings)// 贪心按结束时间排序funcgetMaxPlayTime(nint,playerTimeRange[][]int)int{// 排序sort.Slice(playerTimeRange,func(i,jint)bool{returnplayerTimeRange[i][1]playerTimeRange[j][1]})count:0lastEnd:0fori:0;in;i{currentStart:playerTimeRange[i][0]currentEnd:playerTimeRange[i][1]iflastEndcurrentStart{countlastEndcurrentEnd}}returncount}funcmain(){reader:bufio.NewReader(os.Stdin)line1,_:reader.ReadString(\n)line1strings.TrimSpace(line1)n,_:strconv.Atoi(line1)line2,_:reader.ReadString(\n)line2strings.TrimSpace(line2)records:strings.Split(line2, )playerTimeRange:make([][]int,n)fori:0;in;i{time:strings.Split(records[i],,)start,_:strconv.Atoi(time[0])end,_:strconv.Atoi(time[1])playerTimeRange[i][]int{start,end}}res:getMaxPlayTime(n,playerTimeRange)fmt.Println(res)}C语言#includestdio.h#includestdlib.h#includestring.h// 排序用结构体typedefstruct{intstart;intend;}Interval;// 按结束时间排序intcmp(constvoid*a,constvoid*b){return((Interval*)a)-end-((Interval*)b)-end;}// 贪心算法intgetMaxPlayTime(intn,Interval*arr){qsort(arr,n,sizeof(Interval),cmp);intcount0;intlastEnd0;for(inti0;in;i){if(lastEndarr[i].start){count;lastEndarr[i].end;}}returncount;}intmain(){intn;scanf(%d,n);getchar();// 吃掉换行charinput[100000];fgets(input,sizeof(input),stdin);Interval arr[10000];inti0;char*tokenstrtok(input, );while(token!NULL){intstart,end;sscanf(token,%d,%d,start,end);arr[i].startstart;arr[i].endend;i;tokenstrtok(NULL, );}intresgetMaxPlayTime(n,arr);printf(%d,res);return0;}