0048.安排讲座.md

安排讲座

题目链接

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 比较函数，按结束时间从小到大排序
bool compare(vector<int>& a, vector<int>& b) {
    return a[1] < b[1];
}

// 计算最大出席数
int maximumAttendance(vector<vector<int>>& schedules) {
    sort(schedules.begin(), schedules.end(), compare); // 对课余时间段进行排序
    int count = 0, end = 0; // 初始化讲座数量为0，结束时间为0
    for (int i = 0; i < schedules.size(); i++) {
        if (end <= schedules[i][0]) { // 如果当前班级的开始时间 >= 已经安排的讲座结束时间
            count++; // 讲座数量+1
            end = schedules[i][1]; // 更新已安排讲座的结束时间为当前班级的结束时间
        }
    }
    return count;
}

int main() {
    int N;
    cin >> N; // 输入班级数量
    vector<vector<int>> schedules(N, vector<int>(2)); // 创建存储课余时间段的二维数组
    for (int i = 0; i < N; i++) {
        cin >> schedules[i][0] >> schedules[i][1]; // 输入班级的开始时间和结束时间
    }
    int result = maximumAttendance(schedules); // 计算最大出席数
    cout << result << endl;
    return 0;
}

Java

/**
 * 思路：贪心算法
 * 
 * 贪心的思路是每次选择局部最优解，最终达到全局最优解。
 * 在这个问题中，我们希望尽可能多的安排讲座，因此我们需要选择班级的课余时间段来最大化讲座的数量。
 * 
 * 首先，对班级课余时间段进行排序，按结束时间从小到大排序。
 * 这是希望选择结束时间早的班级，以便留更多的时间给其他班级。
 * 
 * 其次，初始化一个计数器 count 为 0，表示当前安排的讲座为 0，
 * 以及一个变量 end，表示当前已经安排的讲座的结束时间。
 * 
 * 遍历排序后的课余时间段信息：
 *   if (当前班级的开始时间 >= 已经安排的讲座结束时间) {
 *       安排的讲座数量++;
 *       将已经安排的讲座结束时间设置为当前班级的结束时间;
 *   }
 */

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[N][2] schedules = new int[][];
        for (int i = 0; i < N; i++) {
            schedules[i][0] = scanner.nextInt();
            schedules[i][1] = scanner.nextInt();
        }
        System.out.println(maximumAttendance())
    }

    public int maximumAttendance (int[][] schedules) {
        Arrays.sort(schedules, (a, b) -> a[1] - b[1]);
        int count = 0, end = 0;
        for(int i = 0; i < schedules.length; i++){
            if(end <= schedules[i][0]){
                count++;
                end = schedules[i][1];     // 时间点往后推
            }
        }
        return count;
    }
}

Python

# 贪心算法
N = int(input())
lst = []
for i in range(N):
    start, end = list(map(int, input().split()))
    lst.append([start, end])


def classes(N, lst):
    # 按照结束时间从小到大排序
    lst.sort(key=lambda x: x[1])
    count = [lst[0]]
    for i in range(1, N):
        # 记录新班级起始时间在已记录班级结束时间之后的
        if lst[i][0] >= count[-1][1]:
            count.append(lst[i])
        else:
            continue

    return len(count)


ans = classes(N, lst)
print(ans)

Go

Js

C

#include <stdio.h>
#include <stdlib.h>

// 结构体存储班级的开始时间和结束时间
typedef struct {
    int start;
    int end;
} Schedule;

// 比较函数，按结束时间从小到大排序
int compare(const void* a, const void* b) {
    Schedule* schedule_a = (Schedule*)a;
    Schedule* schedule_b = (Schedule*)b;
    return schedule_a->end - schedule_b->end;
}

// 计算最大出席数
int maximumAttendance(Schedule* schedules, int n) {
    qsort(schedules, n, sizeof(Schedule), compare); // 对课余时间段进行排序
    int count = 0, end = 0; // 初始化讲座数量为0，结束时间为0
    for (int i = 0; i < n; i++) {
        if (end <= schedules[i].start) { // 如果当前班级的开始时间 >= 已经安排的讲座结束时间
            count++; // 讲座数量+1
            end = schedules[i].end; // 更新已安排讲座的结束时间为当前班级的结束时间
        }
    }
    return count;
}

int main() {
    int N;
    scanf("%d", &N); // 输入班级数量
    Schedule* schedules = (Schedule*)malloc(N * sizeof(Schedule)); // 创建存储课余时间段的结构体数组
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &schedules[i].start, &schedules[i].end); // 输入班级的开始时间和结束时间
    }
    int result = maximumAttendance(schedules, N); // 计算最大出席数
    printf("%d\n", result);

    free(schedules);
    return 0;
}