电影放映调度问题(C/Py/Java/Js/Go)题解华为笔试真题 6月24号 非AI方向第一题 100分题型题目内容某电影院有111块银幕每天需要安排多部电影在不同时段进行放映。每部电影有固定的放映时长和要求的放映时间段且每个被选中放映的电影确保在对应时段能够完整占用。由于每块银幕同一时间只能放映一部电影需要合理规划使得每天能够放映的电影数量最多。如果第一场电影结束时间与第二场电影的开始时间相同能够连续放映。给定nnn部电影的放映时间区间请计算最多可以放映多少部电影。输入描述第一行:nnn(电影数量) ,1≤n≤1051 \le n \le 10^51≤n≤105接下来nnn行: 每行两个整数start[i]start[i]start[i]和end[i]end[i]end[i], 表示第iii部电影的放映开始时间和结束时间,0≤start[i]end[i]≤14400 \le start[i] end[i] \le 14400≤start[i]end[i]≤1440(一天内的分钟数) (时间以分钟表示,111小时为606060分钟; 如9:005409:00 5409:00540,12:0072012:00 72012:00720)输出描述一个整数: 最多可以放映的电影数量样例1输入3 540 660 540 600 660 780输出2说明最多可以222部电影, 可以选择540540540-660660660和660660660-780780780, 或者540540540-600600600和660660660-780780780样例2输入5 0 1000 100 900 200 800 300 700 400 600输出1说明因为各电影的播放时间均有重叠, 所以最多可以有一部电影播放题解和思路思路实现思路贪心这类求不重叠区间是一种常见贪心题型。贪心基于尽可能选择结束时间早的区间将更多时间留给后续活动从而达到选择尽可能多的区间数量。先对时间区间按照结束时间升序排序。从前往后遇到不冲突的区间进行选择即可然后记录选择区间数量。算法总体时间复杂度为OnlognC#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;vectorpairint,intrange(n);for(inti0;in;i){intstart,end;cinstartend;range[i]{start,end};}// 按终止时间升序sort(range.begin(),range.end(),[](pairint,intp1,pairint,intp2){returnp1.secondp2.second;});// 贪心能选择就选择intcnt0;intlastEnd-1;for(inti0;in;i){if(range[i].firstlastEnd){cnt;lastEndrange[i].second;}}coutcnt;return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intnInteger.parseInt(br.readLine());int[][]rangenewint[n][2];for(inti0;in;i){String[]strsbr.readLine().split( );range[i][0]Integer.parseInt(strs[0]);range[i][1]Integer.parseInt(strs[1]);}// 按终止时间升序Arrays.sort(range,(a,b)-Integer.compare(a[1],b[1]));// 贪心能选择就选择intcnt0;intlastEnd-1;for(inti0;in;i){if(range[i][0]lastEnd){cnt;lastEndrange[i][1];}}System.out.print(cnt);}}pythonimportsys nint(sys.stdin.readline())range_list[]for_inrange(n):start,endmap(int,sys.stdin.readline().split())range_list.append([start,end])# 按终止时间升序range_list.sort(keylambdax:x[1])# 贪心能选择就选择cnt0last_end-1forstart,endinrange_list:ifstartlast_end:cnt1last_endendprint(cnt)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line);});rl.on(close,(){letidx0;constnNumber(input[idx]);constrange[];for(leti0;in;i){const[start,end]input[idx].split( ).map(Number);range.push([start,end]);}// 按终止时间升序range.sort((a,b)a[1]-b[1]);// 贪心能选择就选择letcnt0;letlastEnd-1;for(leti0;in;i){if(range[i][0]lastEnd){cnt;lastEndrange[i][1];}}console.log(cnt);});Gopackagemainimport(bufiofmtossort)typePairstruct{startintendint}funcmain(){in:bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,n)ranges:make([]Pair,n)fori:0;in;i{fmt.Fscan(in,ranges[i].start,ranges[i].end)}// 按终止时间升序sort.Slice(ranges,func(i,jint)bool{returnranges[i].endranges[j].end})// 贪心能选择就选择cnt:0lastEnd:-1fori:0;in;i{ifranges[i].startlastEnd{cntlastEndranges[i].end}}fmt.Print(cnt)}