#P3234. 观看文艺汇演问题(200分)
-
1000ms
Tried: 115
Accepted: 38
Difficulty: 5
所属公司 :
华为od
观看文艺汇演问题(200分)
题目描述
为了庆祝中国共产党成立 100 周年,某公园将举行多场文艺表演,很多演出都是同时进行。
一个人只能同时观看一场演出,且不能迟到早退。
由于演出分布在不同的演出场地,所以连续观看的演出最少有 15 分钟的时间间隔。
小明是一个狂热的文艺迷,想观看尽可能多的演出。
现给出演出时间表,请帮小明计算他最多能观看几场演出。
思路
经典区间贪心问题,求最多不相交区间个数
步骤如下:
-
整理数据: 计算每场演出的开始时间和结束时间。
-
排序: 按照演出的结束时间从早到晚排序。
-
选择活动:
- 初始化上一个活动的结束时间为一个较小的值(如 -15)。
- 遍历排序后的活动列表,对于每个活动:
- 如果当前活动的开始时间 >= 上一个活动的结束时间 + 15,那么选择该活动,并更新上一个活动的结束时间。
代码分析
-
结构体定义: 使用结构体存储每场演出的开始时间和结束时间。
-
排序: 使用
std::sort按照演出的结束时间进行排序。 -
贪心选择: 遍历排序后的活动列表,按照上述选择条件进行选择。
cpp
#include <iostream> // 引入输入输出流库
#include <algorithm> // 引入算法库,用于排序
#include <vector> // 引入向量库,支持动态数组
using namespace std;
// 定义一个结构体 Show,用于表示每场演出
struct Show {
int start; // 演出的开始时间
int end; // 演出的结束时间
};
// 比较函数,用于对演出按结束时间进行排序
bool cmp(const Show &a, const Show &b) {
return a.end < b.end; // 若 a 的结束时间小于 b 的结束时间,则返回 true
}
int main() {
int N; // 演出场数
cin >> N; // 读取演出场数
vector<Show> shows(N); // 创建一个大小为 N 的动态数组,存储每场演出
// 读取每场演出的开始时间和持续时间
for (int i = 0; i < N; ++i) {
int T, L; // T 为开始时间,L 为持续时间
cin >> T >> L; // 从输入读取 T 和 L
shows[i].start = T; // 设置演出的开始时间
shows[i].end = T + L; // 计算演出的结束时间
}
// 按照演出的结束时间排序
sort(shows.begin(), shows.end(), cmp);
int count = 0; // 记录可以观看的演出场数
int last_end = -15; // 初始化上一个演出的结束时间为 -15,确保第一个活动可以被选中
// 遍历排序后的演出列表
for (int i = 0; i < N; ++i) {
// 如果当前演出的开始时间大于等于上一个演出结束时间 + 15分钟
if (shows[i].start >= last_end + 15) {
++count; // 计数可观看的演出场数加一
last_end = shows[i].end; // 更新上一个演出的结束时间
}
}
cout << count << endl; // 输出可以观看的最多演出场数
return 0; // 程序结束
}
python
# 读取演出场数 N
N = int(input())
# 创建一个空列表,用于存储演出的开始时间和结束时间
shows = []
# 循环 N 次,读取每场演出的开始时间和持续时间
for _ in range(N):
T, L = map(int, input().split()) # 从输入读取开始时间 T 和持续时间 L
shows.append((T, T + L)) # 将演出的开始时间和结束时间 (T, T + L) 以元组形式添加到 shows 列表中
# 按照演出的结束时间进行排序
shows.sort(key=lambda x: x[1]) # x[1] 代表演出的结束时间
# 初始化计数器,用于记录最多可以观看的演出场数
count = 0
# 初始化上一个演出的结束时间为 -15,确保第一个演出可以被选中
last_end = -15
# 遍历排序后的演出列表
for show in shows:
# 如果当前演出的开始时间大于等于上一个演出的结束时间 + 15分钟
if show[0] >= last_end + 15:
count += 1 # 计数可观看的演出场数加一
last_end = show[1] # 更新上一个演出的结束时间为当前演出的结束时间
# 输出最多可以观看的演出场数
print(count)
java
import java.util.*; // 引入 Java 的工具包,包含集合、输入输出等类
public class Main {
// 定义一个内部类 Show,用于表示每场演出
static class Show implements Comparable<Show> {
int start; // 演出的开始时间
int end; // 演出的结束时间
// Show 构造函数,用于初始化开始时间和结束时间
Show(int start, int end) {
this.start = start; // 设置开始时间
this.end = end; // 设置结束时间
}
// 实现 compareTo 方法,用于根据结束时间进行比较
public int compareTo(Show other) {
return this.end - other.end; // 如果当前对象的结束时间小于 other 的结束时间,则返回负值
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象用于读取输入
int n = scanner.nextInt(); // 读取演出场数 n
Show[] shows = new Show[n]; // 创建一个 Show 数组,用于存储每场演出
// 循环 n 次,读取每场演出的开始时间和持续时间
for (int i = 0; i < n; i++) {
int T = scanner.nextInt(); // 读取开始时间 T
int L = scanner.nextInt(); // 读取持续时间 L
shows[i] = new Show(T, T + L); // 创建 Show 对象,并将其存入数组,结束时间为 T + L
}
Arrays.sort(shows); // 对演出数组按结束时间进行排序
int count = 0; // 初始化可观看演出场数计数器
int last_end = -15; // 初始化上一个演出的结束时间为 -15,确保第一个活动可以被选中
// 遍历排序后的演出列表
for (Show show : shows) {
// 如果当前演出的开始时间大于等于上一个演出的结束时间 + 15分钟
if (show.start >= last_end + 15) {
count++; // 计数可观看的演出场数加一
last_end = show.end; // 更新上一个演出的结束时间为当前演出的结束时间
}
}
System.out.println(count); // 输出最多可以观看的演出场数
}
}
题目内容
为了庆祝中国共产党成立 100 周年,某公园将举行多场文艺表演,很多演出都是同时进行。
一个人只能同时观看一场演出,且不能迟到早退。
由于演出分布在不同的演出场地,所以连续观看的演出最少有 15 分钟的时间间隔。
小红是一个狂热的文艺迷,想观看尽可能多的演出。
现给出演出时间表,请帮小红计算他最多能观看几场演出。
输入描述
第一行为一个数 N,表示演出场数
- 1≤N≤1000
接下来 N 行,每行有被空格分割的整数,第一个整数 T 表示演出的开始时间,第二个整数 L 表示演出的持续时间
- T 和 L 的单位为分钟
- 0≤T≤1440
- 0<L≤180
输出描述
输出最多能观看的演出场数。
样例1
输入
2
720 120
840 120
输出
1
说明
两场演出间隔时间为 0,不满足最小 15 分钟时间间隔的要求,所以最多只能观看一场演出
样例2
输入
2
0 60
90 60
输出
2
说明
两场演出间隔大于 15 分钟,都能观看到