题目描述

为了庆祝中国共产党成立 $100$ 周年，某公园将举行多场文艺表演，很多演出都是同时进行。

一个人只能同时观看一场演出，且不能迟到早退。

由于演出分布在不同的演出场地，所以连续观看的演出最少有 $15$ 分钟的时间间隔。

小明是一个狂热的文艺迷，想观看尽可能多的演出。

现给出演出时间表，请帮小明计算他最多能观看几场演出。

思路

经典区间贪心问题，求最多不相交区间个数

步骤如下：

1. 整理数据： 计算每场演出的开始时间和结束时间。

2. 排序： 按照演出的结束时间从早到晚排序。

3. 选择活动：

   • 初始化上一个活动的结束时间为一个较小的值（如 -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$ 分钟，都能观看到