华为非AI方向笔试真题 6月24号【电影放映调度问题】

电影放映调度问题(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:00=5409:00 = 5409:00=540,12:00=72012:00 = 72012:00=720)

输出描述

一个整数: 最多可以放映的电影数量

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

说明
因为各电影的播放时间均有重叠, 所以最多可以有一部电影播放

题解和思路

思路

实现思路：贪心

1. 这类求不重叠区间是一种常见贪心题型。贪心基于尽可能选择结束时间早的区间，将更多时间留给后续活动，从而达到选择尽可能多的区间数量。
2. 先对时间区间按照结束时间升序排序。
3. 从前往后遇到不冲突的区间进行选择即可，然后记录选择区间数量。
4. 算法总体时间复杂度为O（nlogn）

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;vector<pair<int,int>>range(n);for(inti=0;i<n;i++){intstart,end;cin>>start>>end;range[i]={start,end};}// 按终止时间升序sort(range.begin(),range.end(),[](pair<int,int>&p1,pair<int,int>&p2){returnp1.second<p2.second;});// 贪心能选择就选择intcnt=0;intlastEnd=-1;for(inti=0;i<n;i++){if(range[i].first>=lastEnd){cnt++;lastEnd=range[i].second;}}cout<<cnt;return0;}

Java

importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intn=Integer.parseInt(br.readLine());int[][]range=newint[n][2];for(inti=0;i<n;i++){String[]strs=br.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]));// 贪心能选择就选择intcnt=0;intlastEnd=-1;for(inti=0;i<n;i++){if(range[i][0]>=lastEnd){cnt++;lastEnd=range[i][1];}}System.out.print(cnt);}}

python

importsys n=int(sys.stdin.readline())range_list=[]for_inrange(n):start,end=map(int,sys.stdin.readline().split())range_list.append([start,end])# 按终止时间升序range_list.sort(key=lambdax:x[1])# 贪心能选择就选择cnt=0last_end=-1forstart,endinrange_list:ifstart>=last_end:cnt+=1last_end=endprint(cnt)

Javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on('line',line=>{input.push(line);});rl.on('close',()=>{letidx=0;constn=Number(input[idx++]);constrange=[];for(leti=0;i<n;i++){const[start,end]=input[idx++].split(" ").map(Number);range.push([start,end]);}// 按终止时间升序range.sort((a,b)=>a[1]-b[1]);// 贪心能选择就选择letcnt=0;letlastEnd=-1;for(leti=0;i<n;i++){if(range[i][0]>=lastEnd){cnt++;lastEnd=range[i][1];}}console.log(cnt);});

Go

packagemainimport("bufio""fmt""os""sort")typePairstruct{startintendint}funcmain(){in:=bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,&n)ranges:=make([]Pair,n)fori:=0;i<n;i++{fmt.Fscan(in,&ranges[i].start,&ranges[i].end)}// 按终止时间升序sort.Slice(ranges,func(i,jint)bool{returnranges[i].end<ranges[j].end})// 贪心能选择就选择cnt:=0lastEnd:=-1fori:=0;i<n;i++{ifranges[i].start>=lastEnd{cnt++lastEnd=ranges[i].end}}fmt.Print(cnt)}