LLM推理批次最大化(C/Py/Java /Js/Go/C)题解华为OD机试新系统真题 华为OD上机考试新系统真题 8月12号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容大语言模型推理时显存中有一个 KV Cache用于存储各请求的键值对。现有N NN个推理请求排队第i ii个请求需要占用 KV Cache 中一段连续位置[ L i , R i ] [L_i, R_i][Li,Ri]。每个位置同一时间只能分配给一个请求。请选出尽可能多的请求使它们的区间互不重叠从而最大化批次的吞吐量。补充说明[1, 3]和[3, 5]被认为是重叠。输入描述requests由N NN个推理请求构成的二维数组requests[i]表示第i ii个推理请求其内容为[ L i , R i ] [L_i, R_i][Li,Ri]。数组长度N NN满足1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105。每个位置[ L i , R i ] [L_i, R_i][Li,Ri]满足0 ≤ L i ≤ R i ≤ 10 9 0 \le L_i \le R_i \le 10^90≤Li≤Ri≤109。输出描述一个整数表示最多可选多少个不重叠区间的请求。样例1输入1,3 2,5 4,7 6,9 8,10 11,12输出4说明选[1,3],[4,7],[8,10],[11,12]共4个区间互不重叠为最大可行数。样例2输入1,3 2,4 3,3 4,4输出2说明选[1,3],[4,4]共2个不重叠的区间。样例3输入3,5输出1说明只有1个请求可选择的个数就为1。题解思路贪心经典的区间调度问题对于这类在若干个时间区间内求最多不重叠时间区间数量的题都可以采用以下思路处理。首先将时间区间按照结束时间进行升序排序。从前往后选择区间当前区间开始时间大于上一个区间的结束时间就选择。贪心原理基于上个区间结束时间越早越能留给后续区间更多时间因此代码逻辑为对输入区间按照结束时间进行升序排序。定义ans表示选择区间数量定义lastEnd记录上次选择区间的结束时间。从前往后遍历时间区间{start, end}, 当start lastEnd时更新ans, lastEnd end最终ans的值就是结果。本题处理逻辑和前段时间考过的 华为OD新系统机试真题 4.26 -最大化游戏试玩资格分发逻辑基本完全一致。c#includebits/stdc.h#includevectorusingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vectorstringsplit(conststringstr,conststringdelimiter){vectorstringresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(str.substr(start,end-start));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(str.substr(start));returnresult;}intsolve(vectorvectorintrequests){// 按照结束时间进行升序sort(requests.begin(),requests.end(),[](vectorinta,vectorintb){returna[1]b[1];});intnrequests.size();intans0;intlastEnd-1;for(inti0;in;i){intstartrequests[i][0];intendrequests[i][1];if(startlastEnd){ans;lastEndend;}}returnans;}intmain(){string input;getline(cin,input);vectorvectorintrequests;vectorstringtmpsplit(input, );// 分割字符串获取二维区间数组for(inti0;itmp.size();i){vectorstringtmp1split(tmp[i],,);requests.push_back({stoi(tmp1[0]),stoi(tmp1[1])});}coutsolve(requests);return0;}Javaimportjava.util.*;publicclassMain{staticintsolve(Listint[]requests){// 按照结束时间进行升序requests.sort((a,b)-Integer.compare(a[1],b[1]));intnrequests.size();intans0;intlastEnd-1;for(inti0;in;i){intstartrequests.get(i)[0];intendrequests.get(i)[1];if(startlastEnd){ans;lastEndend;}}returnans;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);Stringinputscanner.nextLine();Listint[]requestsnewArrayList();// 分割字符串获取二维区间数组String[]tmpinput.split( );for(inti0;itmp.length;i){String[]tmp1tmp[i].split(,);requests.add(newint[]{Integer.parseInt(tmp1[0]),Integer.parseInt(tmp1[1])});}System.out.println(solve(requests));}}Python# 通用切割函数Python 自带 split不需要自定义defsolve(requests):# 按照结束时间进行升序requests.sort(keylambdax:x[1])nlen(requests)ans0last_end-1foriinrange(n):startrequests[i][0]endrequests[i][1]ifstartlast_end:ans1last_endendreturnans input_strinput()requests[]# 分割字符串获取二维区间数组tmpinput_str.split( )foriinrange(len(tmp)):tmp1tmp[i].split(,)requests.append([int(tmp1[0]),int(tmp1[1])])print(solve(requests))JavaScriptfunctionsolve(requests){// 按照结束时间进行升序requests.sort((a,b)a[1]-b[1]);constnrequests.length;letans0;letlastEnd-1;for(leti0;in;i){conststartrequests[i][0];constendrequests[i][1];if(startlastEnd){ans;lastEndend;}}returnans;}constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});rl.on(line,(input){constrequests[];// 分割字符串获取二维区间数组consttmpinput.split( );for(leti0;itmp.length;i){consttmp1tmp[i].split(,);requests.push([Number(tmp1[0]),Number(tmp1[1])]);}console.log(solve(requests));rl.close();});Gopackagemainimport(bufiofmtossortstrconvstrings)funcsolve(requests[][]int)int{// 按照结束时间进行升序sort.Slice(requests,func(i,jint)bool{returnrequests[i][1]requests[j][1]})n:len(requests)ans:0lastEnd:-1fori:0;in;i{start:requests[i][0]end:requests[i][1]ifstartlastEnd{anslastEndend}}returnans}funcmain(){reader:bufio.NewReader(os.Stdin)input,_:reader.ReadString(\n)inputstrings.TrimSpace(input)varrequests[][]int// 分割字符串获取二维区间数组tmp:strings.Split(input, )fori:0;ilen(tmp);i{tmp1:strings.Split(tmp[i],,)start,_:strconv.Atoi(tmp1[0])end,_:strconv.Atoi(tmp1[1])requestsappend(requests,[]int{start,end})}fmt.Println(solve(requests))}C语言#includestdio.h#includestdlib.h#includestring.htypedefstruct{intstart;intend;}Request;// 按照结束时间进行升序intcompare(constvoid*a,constvoid*b){Request*x(Request*)a;Request*y(Request*)b;returnx-end-y-end;}intsolve(Request requests[],intn){// 按照结束时间进行升序qsort(requests,n,sizeof(Request),compare);intans0;intlastEnd-1;for(inti0;in;i){intstartrequests[i].start;intendrequests[i].end;if(startlastEnd){ans;lastEndend;}}returnans;}intmain(){charinput[10000009];Request requests[100005];intn0;fgets(input,sizeof(input),stdin);input[strcspn(input,\n)]\0;// 分割字符串获取二维区间数组char*tokenstrtok(input, );while(token!NULL){intstart,end;sscanf(token,%d,%d,start,end);requests[n].startstart;requests[n].endend;n;tokenstrtok(NULL, );}printf(%d,solve(requests,n));return0;} LLM推理批次最大化(C/Py/Java /Js/Go/C)题解华为OD机试新系统真题 华为OD上机考试新系统真题 8月12号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容大语言模型推理时显存中有一个 KV Cache用于存储各请求的键值对。现有N NN个推理请求排队第i ii个请求需要占用 KV Cache 中一段连续位置[ L i , R i ] [L_i, R_i][Li,Ri]。每个位置同一时间只能分配给一个请求。请选出尽可能多的请求使它们的区间互不重叠从而最大化批次的吞吐量。补充说明[1, 3]和[3, 5]被认为是重叠。输入描述requests由N NN个推理请求构成的二维数组requests[i]表示第i ii个推理请求其内容为[ L i , R i ] [L_i, R_i][Li,Ri]。数组长度N NN满足1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105。每个位置[ L i , R i ] [L_i, R_i][Li,Ri]满足0 ≤ L i ≤ R i ≤ 10 9 0 \le L_i \le R_i \le 10^90≤Li≤Ri≤109。输出描述一个整数表示最多可选多少个不重叠区间的请求。样例1输入1,3 2,5 4,7 6,9 8,10 11,12输出4说明选[1,3],[4,7],[8,10],[11,12]共4个区间互不重叠为最大可行数。样例2输入1,3 2,4 3,3 4,4输出2说明选[1,3],[4,4]共2个不重叠的区间。样例3输入3,5输出1说明只有1个请求可选择的个数就为1。题解思路贪心经典的区间调度问题对于这类在若干个时间区间内求最多不重叠时间区间数量的题都可以采用以下思路处理。首先将时间区间按照结束时间进行升序排序。从前往后选择区间当前区间开始时间大于上一个区间的结束时间就选择。贪心原理基于上个区间结束时间越早越能留给后续区间更多时间因此代码逻辑为对输入区间按照结束时间进行升序排序。定义ans表示选择区间数量定义lastEnd记录上次选择区间的结束时间。从前往后遍历时间区间{start, end}, 当start lastEnd时更新ans, lastEnd end最终ans的值就是结果。本题处理逻辑和前段时间考过的 华为OD新系统机试真题 4.26 -最大化游戏试玩资格分发逻辑基本完全一致。c#includebits/stdc.h#includevectorusingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vectorstringsplit(conststringstr,conststringdelimiter){vectorstringresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(str.substr(start,end-start));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(str.substr(start));returnresult;}intsolve(vectorvectorintrequests){// 按照结束时间进行升序sort(requests.begin(),requests.end(),[](vectorinta,vectorintb){returna[1]b[1];});intnrequests.size();intans0;intlastEnd-1;for(inti0;in;i){intstartrequests[i][0];intendrequests[i][1];if(startlastEnd){ans;lastEndend;}}returnans;}intmain(){string input;getline(cin,input);vectorvectorintrequests;vectorstringtmpsplit(input, );// 分割字符串获取二维区间数组for(inti0;itmp.size();i){vectorstringtmp1split(tmp[i],,);requests.push_back({stoi(tmp1[0]),stoi(tmp1[1])});}coutsolve(requests);return0;}Javaimportjava.util.*;publicclassMain{staticintsolve(Listint[]requests){// 按照结束时间进行升序requests.sort((a,b)-Integer.compare(a[1],b[1]));intnrequests.size();intans0;intlastEnd-1;for(inti0;in;i){intstartrequests.get(i)[0];intendrequests.get(i)[1];if(startlastEnd){ans;lastEndend;}}returnans;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);Stringinputscanner.nextLine();Listint[]requestsnewArrayList();// 分割字符串获取二维区间数组String[]tmpinput.split( );for(inti0;itmp.length;i){String[]tmp1tmp[i].split(,);requests.add(newint[]{Integer.parseInt(tmp1[0]),Integer.parseInt(tmp1[1])});}System.out.println(solve(requests));}}Python# 通用切割函数Python 自带 split不需要自定义defsolve(requests):# 按照结束时间进行升序requests.sort(keylambdax:x[1])nlen(requests)ans0last_end-1foriinrange(n):startrequests[i][0]endrequests[i][1]ifstartlast_end:ans1last_endendreturnans input_strinput()requests[]# 分割字符串获取二维区间数组tmpinput_str.split( )foriinrange(len(tmp)):tmp1tmp[i].split(,)requests.append([int(tmp1[0]),int(tmp1[1])])print(solve(requests))JavaScriptfunctionsolve(requests){// 按照结束时间进行升序requests.sort((a,b)a[1]-b[1]);constnrequests.length;letans0;letlastEnd-1;for(leti0;in;i){conststartrequests[i][0];constendrequests[i][1];if(startlastEnd){ans;lastEndend;}}returnans;}constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});rl.on(line,(input){constrequests[];// 分割字符串获取二维区间数组consttmpinput.split( );for(leti0;itmp.length;i){consttmp1tmp[i].split(,);requests.push([Number(tmp1[0]),Number(tmp1[1])]);}console.log(solve(requests));rl.close();});Gopackagemainimport(bufiofmtossortstrconvstrings)funcsolve(requests[][]int)int{// 按照结束时间进行升序sort.Slice(requests,func(i,jint)bool{returnrequests[i][1]requests[j][1]})n:len(requests)ans:0lastEnd:-1fori:0;in;i{start:requests[i][0]end:requests[i][1]ifstartlastEnd{anslastEndend}}returnans}funcmain(){reader:bufio.NewReader(os.Stdin)input,_:reader.ReadString(\n)inputstrings.TrimSpace(input)varrequests[][]int// 分割字符串获取二维区间数组tmp:strings.Split(input, )fori:0;ilen(tmp);i{tmp1:strings.Split(tmp[i],,)start,_:strconv.Atoi(tmp1[0])end,_:strconv.Atoi(tmp1[1])requestsappend(requests,[]int{start,end})}fmt.Println(solve(requests))}C语言#includestdio.h#includestdlib.h#includestring.htypedefstruct{intstart;intend;}Request;// 按照结束时间进行升序intcompare(constvoid*a,constvoid*b){Request*x(Request*)a;Request*y(Request*)b;returnx-end-y-end;}intsolve(Request requests[],intn){// 按照结束时间进行升序qsort(requests,n,sizeof(Request),compare);intans0;intlastEnd-1;for(inti0;in;i){intstartrequests[i].start;intendrequests[i].end;if(startlastEnd){ans;lastEndend;}}returnans;}intmain(){charinput[10000009];Request requests[100005];intn0;fgets(input,sizeof(input),stdin);input[strcspn(input,\n)]\0;// 分割字符串获取二维区间数组char*tokenstrtok(input, );while(token!NULL){intstart,end;sscanf(token,%d,%d,start,end);requests[n].startstart;requests[n].endend;n;tokenstrtok(NULL, );}printf(%d,solve(requests,n));return0;} 
