当前位置：首页 > news >正文

华为OD机试 - 计算最多能观看几场演出（Python/JS/C/C++ 2024 E卷 200分）

news 2024/10/22 10:44:36

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

为了庆祝中国共产党成立100周年，某公园将举行多场文艺表演，很多演出都是同时进行，一个人只能同时观看一场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有15分钟的时间间隔。

小明是一个狂热的文艺迷，想观看尽可能多的演出，现给出演出时间表，请帮小明计算他最多能观看几场演出。

二、输入描述

第一行为一个数N,表示演出场数，1 <= N<=1000,接下来N行，每行有被空格分割的两个整数；
第一个整数T表示演出的开始时间，第二个整数L表示演出的持续时间；

T和L的单位为分钟，0 <=T <=1440, 0 <= L <= 100

三、输出描述

输出最多能观看的演出场数。

四、测试用例

1、输入

3
100 120
240 150
400 100

2、输出

3、说明

第一场100开始，持续120分钟，结束时220；
第一场220结束，距离第二场开始时间240，大于15分钟，时间来得及，观看场次+1；
第二场390结束，距离第三场开始时间400，小于15分钟，来不及了。

在这里插入图片描述

五、解题思路

输入演出场数N；
定义演出开始时间+演出结束时间list集合timeList；
输入演出的开始时间T；
输入演出的持续时间L；
初始化timeList集合，并排序；
定义最多能观看的演出场数max；
遍历时间集合timeList；
连续观看的演出最少有15分钟的时间间隔，观看场次+1；
输出最多能观看的演出场数

六、Python算法源码

# Python 代码
import sysdef main():import sys# 读取所有输入input = sys.stdin.read().split()idx = 0# 读取演出场数 NN = int(input[idx])idx += 1timeList = []for _ in range(N):# 读取演出的开始时间 TT = int(input[idx])idx += 1# 读取演出的持续时间 LL = int(input[idx])idx += 1# 计算演出的结束时间endTime = T + L# 将开始时间和结束时间加入列表timeList.append((T, endTime))# 按结束时间降序排序，如果结束时间相同，则按开始时间降序排序timeList.sort(key=lambda x: (-x[1], -x[0]))# 初始化开始时间为第一个演出的开始时间startTime = timeList[0][0]# 最多能观看的演出场数初始化为1max_count = 1# 遍历所有演出for time in timeList:# 当前演出的开始时间curStartTime = time[0]# 当前演出的结束时间curEndTime = time[1]# 如果当前演出的结束时间与之前选择的演出的开始时间间隔至少15分钟if startTime - curEndTime >= 15:# 增加观看的演出数量max_count += 1# 更新开始时间为当前演出的开始时间startTime = curStartTime# 输出最多能观看的演出场数print(max_count)if __name__ == "__main__":main()

七、JavaScript算法源码

// JavaScript 代码
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', (line) => {input = input.concat(line.trim().split(' '));
}).on('close', () => {let idx = 0;// 读取演出场数 Nconst N = parseInt(input[idx++]);let timeList = [];for (let i = 0; i < N; i++) {// 读取演出的开始时间 Tconst T = parseInt(input[idx++]);// 读取演出的持续时间 Lconst L = parseInt(input[idx++]);// 计算演出的结束时间const endTime = T + L;// 将开始时间和结束时间加入列表timeList.push([T, endTime]);}// 按结束时间降序排序，如果结束时间相同，则按开始时间降序排序timeList.sort((a, b) => {if (b[1] === a[1]) {return b[0] - a[0];} else {return b[1] - a[1];}});// 初始化开始时间为第一个演出的开始时间let startTime = timeList[0][0];// 最多能观看的演出场数初始化为1let max = 1;// 遍历所有演出for (let i = 0; i < timeList.length; i++) {const curStartTime = timeList[i][0]; // 当前演出的开始时间const curEndTime = timeList[i][1];   // 当前演出的结束时间// 如果当前演出的结束时间与之前选择的演出的开始时间间隔至少15分钟if (startTime - curEndTime >= 15) {// 增加观看的演出数量max++;// 更新开始时间为当前演出的开始时间startTime = curStartTime;}}// 输出最多能观看的演出场数console.log(max);
});

八、C算法源码

/* C 代码 */
#include <stdio.h>
#include <stdlib.h>// 定义一个结构体来存储演出的开始时间和结束时间
typedef struct {int start;int end;
} Performance;// 比较函数，用于按照结束时间降序排序，如果结束时间相同，则按照开始时间降序排序
int compare(const void* a, const void* b) {Performance* p1 = (Performance*)a;Performance* p2 = (Performance*)b;if (p2->end == p1->end) {return p2->start - p1->start;}return p2->end - p1->end;
}int main(){int N;// 读取演出场数 Nscanf("%d", &N);Performance* timeList = (Performance*)malloc(sizeof(Performance) * N);for(int i = 0; i < N; i++){int T, L;// 读取演出的开始时间 Tscanf("%d", &T);// 读取演出的持续时间 Lscanf("%d", &L);// 计算演出的结束时间timeList[i].start = T;timeList[i].end = T + L;}// 按结束时间降序排序qsort(timeList, N, sizeof(Performance), compare);// 初始化开始时间为第一个演出的开始时间int startTime = timeList[0].start;// 最多能观看的演出场数初始化为1int max = 1;// 遍历所有演出for(int i = 0; i < N; i++){int curStartTime = timeList[i].start; // 当前演出的开始时间int curEndTime = timeList[i].end;     // 当前演出的结束时间// 如果当前演出的结束时间与之前选择的演出的开始时间间隔至少15分钟if(startTime - curEndTime >= 15){// 增加观看的演出数量max++;// 更新开始时间为当前演出的开始时间startTime = curStartTime;}}// 输出最多能观看的演出场数printf("%d\n", max);// 释放分配的内存free(timeList);return 0;
}

九、C++算法源码

// C++ 代码
#include <bits/stdc++.h>
using namespace std;// 定义一个结构体来存储演出的开始时间和结束时间
struct Performance {int start;int end;
};// 比较函数，用于按照结束时间降序排序，如果结束时间相同，则按照开始时间降序排序
bool compare(const Performance &a, const Performance &b) {if(a.end == b.end){return a.start > b.start;}return a.end > b.end;
}int main(){int N;// 读取演出场数 Ncin >> N;vector<Performance> timeList(N);for(int i = 0; i < N; i++){int T, L;// 读取演出的开始时间 Tcin >> T;// 读取演出的持续时间 Lcin >> L;// 计算演出的结束时间timeList[i].start = T;timeList[i].end = T + L;}// 按结束时间降序排序，如果结束时间相同，则按开始时间降序排序sort(timeList.begin(), timeList.end(), compare);// 初始化开始时间为第一个演出的开始时间int startTime = timeList[0].start;// 最多能观看的演出场数初始化为1int max_count = 1;// 遍历所有演出for(auto &performance : timeList){int curStartTime = performance.start; // 当前演出的开始时间int curEndTime = performance.end;     // 当前演出的结束时间// 如果当前演出的结束时间与之前选择的演出的开始时间间隔至少15分钟if(startTime - curEndTime >= 15){// 增加观看的演出数量max_count++;// 更新开始时间为当前演出的开始时间startTime = curStartTime;}}// 输出最多能观看的演出场数cout << max_count << endl;return 0;
}