每日一题——主持人调度（二）

news/2025/2/24 11:50:42

主持人调度（二）

    • 问题描述
      • 输入格式
      • 输出格式
      • 示例
        • 示例 1：
        • 示例 2：
    • 第一种直观解法
      • 代码逻辑详解
      • 贪心算法的关键点
      • 复杂度分析
    • 第二种思路
      • 代码解析
      • 完整代码与注释
      • 算法逻辑总结
      • 复杂度分析
      • 示例验证
        • 输入数据
        • 代码执行过程
          • 1. 提取并排序开始时间和结束时间
          • 2. 双指针遍历
        • 3. 计算结果
      • 结论
      • 验证

在这里插入图片描述
好的，以下是一个整理好的关于“主持人调度问题”的CSDN博客文档内容。你可以根据需要进一步调整格式或补充细节。

问题描述

有 n 个活动即将举办，每个活动都有开始时间与结束时间。第 i 个活动的开始时间是 start_i，结束时间是 end_i。为了成功举办每个活动，需要为每个活动分配一名主持人。一位主持人在同一时间只能参与一个活动，并且需要全程参与活动。换句话说，如果一个主持人参与了第 i 个活动，那么他在 (start_i, end_i) 这个时间段内不能参与其他任何活动。目标是求出为了成功举办所有活动，最少需要多少名主持人。

输入格式

  • n：活动的数量，范围为 1 ≤ n ≤ 10^5。
  • startEnd：一个二维数组，startEnd[i][0] 表示第 i 个活动的开始时间，startEnd[i][1] 表示第 i 个活动的结束时间。时间范围为 -2^32 ≤ start_i ≤ end_i ≤ 2^31 - 1。

输出格式

  • 返回一个整数，表示最少需要的主持人数量。

示例

示例 1：

输入：

2, [[1,2], [2,3]]

输出：

1

说明：只需要一个主持人就能成功举办这两个活动。

示例 2：

输入：

2, [[1,3], [2,4]]

输出：

2

说明：需要两个主持人才能成功举办这两个活动。

第一种直观解法

最开始想的传统思维，每一个活动开始前，看看前面的主持人有没有空闲的，有空闲的，就复用，没有空闲的，就再雇佣一个。

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

// 定义活动结构体，每个活动包含开始时间和结束时间
typedef struct {
    int start;  // 活动的开始时间
    int end;    // 活动的结束时间
} Activity;

// 比较函数，用于 qsort 排序
int compare(const void* a, const void* b) {
    Activity* activity1 = (Activity*)a;  // 将 void* 类型转换为 Activity* 类型
    Activity* activity2 = (Activity*)b;  // 将 void* 类型转换为 Activity* 类型

    // 首先按活动的开始时间排序
    if (activity1->start < activity2->start) return -1;  // 如果活动1的开始时间更早，返回 -1注意可能会越界，所以用比较，而不是相减
    if (activity1->start > activity2->start) return 1;   // 如果活动1的开始时间更晚，返回 1

    // 如果开始时间相同，则按结束时间排序
    if (activity1->end < activity2->end) return -1;  // 如果活动1的结束时间更早，返回 -1
    if (activity1->end > activity2->end) return 1;   // 如果活动1的结束时间更晚，返回 1

    return 0;  // 如果两个活动的开始时间和结束时间都相同，返回 0
}

// 计算最少需要的主持人数量
int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen, int* startEndColLen) {
    // 创建一个数组来存储所有活动的开始时间和结束时间
    Activity activities[n];
    for (int i = 0; i < n; i++) {
        activities[i].start = startEnd[i][0];  // 获取第 i 个活动的开始时间
        activities[i].end = startEnd[i][1];    // 获取第 i 个活动的结束时间
    }

    // 使用 qsort 对活动数组进行排序，排序规则由 compare 函数定义
    qsort(activities, n, sizeof(Activity), compare);

    // 创建一个数组来记录每个主持人的空闲时间
    int hosts[n];  // 假设最多可能需要 n 个主持人
    int hostCount = 0;  // 当前已分配的主持人数量

    // 遍历所有活动，尝试为每个活动分配主持人
    for (int i = 0; i < n; i++) {
        int assigned = 0;  // 标记当前活动是否已经分配了主持人

        // 尝试复用已分配的主持人
        for (int j = 0; j < hostCount; j++) {
            // 如果当前活动的开始时间大于等于某个主持人的空闲时间，则可以复用该主持人
            if (activities[i].start >= hosts[j]) {
                hosts[j] = activities[i].end;  // 更新该主持人的空闲时间为当前活动的结束时间
                assigned = 1;  // 标记当前活动已分配主持人
                break;  // 跳出循环
            }
        }

        // 如果当前活动无法复用任何已分配的主持人，则新增一名主持人
        if (!assigned) {
            hosts[hostCount] = activities[i].end;  // 新增主持人的空闲时间为当前活动的结束时间
            hostCount++;  // 主持人数量加 1
        }
    }

    return hostCount;  // 返回所需的最少主持人数量
}

代码逻辑详解

  1. 活动结构体：

    • 定义了一个 Activity 结构体，包含两个字段：start 和 end，分别表示活动的开始时间和结束时间。

  2. 比较函数：

    • compare 函数用于 qsort 排序。它首先按活动的开始时间排序，如果开始时间相同，则按结束时间排序。
    • 这种排序方式确保了活动按时间顺序排列，便于后续的贪心算法实现。

  3. 活动数组初始化：

    • 遍历输入的二维数组 startEnd，将每个活动的开始时间和结束时间存入 activities 数组。

  4. 排序：

    • 使用 qsort 对活动数组按排序规则进行排序。

  5. 分配主持人：

    • 创建一个数组 hosts 用于记录每个主持人的空闲时间。
    • 遍历排序后的活动数组，尝试为每个活动分配主持人：
      • 如果当前活动的开始时间大于等于某个主持人的空闲时间，则可以复用该主持人，并更新该主持人的空闲时间为当前活动的结束时间。
      • 如果无法复用任何已分配的主持人，则新增一名主持人。

  6. 返回结果：

    • 最终返回所需的最少主持人数量。

贪心算法的关键点

  • 排序：通过排序确保活动按时间顺序排列，便于贪心选择。
  • 复用主持人：尽量复用已有的主持人，避免新增主持人。
  • 空闲时间更新：每次分配活动后，更新主持人的空闲时间。

复杂度分析

  • 时间复杂度：O(n log n)，主要由排序操作决定。
  • 空间复杂度：O(n)，用于存储活动数组和主持人数组。

第二种思路

代码解析

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;  // 比较函数，用于qsort排序，从小到大排序
}
  • cmp函数：这是qsort函数的比较函数，用于对数组进行排序。它将两个指针指向的整数进行比较，返回它们的差值。如果差值为负数，则表示第一个数小于第二个数；如果差值为正数，则表示第一个数大于第二个数。这里实现的是从小到大排序。
int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen, int* startEndColLen) {
    // 分配内存用于存储所有活动的开始时间和结束时间
    int* Start = (int*)malloc(sizeof(int) * n);
    int* End = (int*)malloc(sizeof(int) * n);

    // 将输入的活动开始时间和结束时间分别存储到Start和End数组中
    for (int i = 0; i < n; i++) {
        Start[i] = startEnd[i][0];  // 第i个活动的开始时间
        End[i] = startEnd[i][1];    // 第i个活动的结束时间
    }

    // 对开始时间和结束时间分别进行排序
    qsort(Start, n, sizeof(int), cmp);
    qsort(End, n, sizeof(int), cmp);
  • Start和End数组：分别存储所有活动的开始时间和结束时间。
  • qsort函数：对Start和End数组分别进行排序。排序后，Start数组中的元素按从小到大的顺序表示所有活动的开始时间，End数组中的元素按从小到大的顺序表示所有活动的结束时间。
    int i, j;
    for (i = 1, j = 0; i < n; i++) {
        if (Start[i] >= End[j]) {
            j++;  // 如果当前活动的开始时间大于等于某个活动的结束时间，说明可以复用主持人
        }
    }
  • 双指针逻辑：
    • i指针遍历所有活动的开始时间（Start数组）。
    • j指针遍历所有活动的结束时间（End数组）。
    • 对于每个活动的开始时间Start[i]，检查是否存在一个活动的结束时间End[j]，使得Start[i] >= End[j]。如果满足条件，说明当前活动可以复用已经结束的活动的主持人，因此j指针向前移动。
    • 如果Start[i] < End[j]，说明当前活动无法复用任何已结束的活动的主持人，需要新增一名主持人。

可以理解为每次活动开始的时候，问下前面的活动有没有结束的，赶紧来个主持人，由于end已经排序好了，所以不用担心，只要比较第j个(初始为0)就好了，第一个不行，之后更加完蛋，然后第一个活动主持人如果被叫过去，j++;

    return i - j;  // 返回需要的主持人数量
}
  • 返回值：
    • i - j表示需要的主持人数量。i是总活动数量，j表示可以复用的活动数量。因此，i - j就是需要新增的主持人数量。

完整代码与注释

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;  // 比较函数，用于qsort排序，从小到大排序
}

int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen, int* startEndColLen) {
    // 分配内存用于存储所有活动的开始时间和结束时间
    int* Start = (int*)malloc(sizeof(int) * n);
    int* End = (int*)malloc(sizeof(int) * n);

    // 将输入的活动开始时间和结束时间分别存储到Start和End数组中
    for (int i = 0; i < n; i++) {
        Start[i] = startEnd[i][0];  // 第i个活动的开始时间
        End[i] = startEnd[i][1];    // 第i个活动的结束时间
    }

    // 对开始时间和结束时间分别进行排序
    qsort(Start, n, sizeof(int), cmp);
    qsort(End, n, sizeof(int), cmp);

    // 双指针逻辑：i遍历开始时间，j遍历结束时间
    int i, j;
    for (i = 1, j = 0; i < n; i++) {
        if (Start[i] >= End[j]) {
            j++;  // 如果当前活动的开始时间大于等于某个活动的结束时间，说明可以复用主持人
        }
    }

    // 返回需要的主持人数量
    return i - j;  // i是总活动数量，j是可复用的活动数量
}

算法逻辑总结

  1. 分离和排序：

    • 将所有活动的开始时间和结束时间分别存储到两个数组Start和End中。
    • 对Start和End数组分别进行排序。

  2. 双指针遍历：

    • 使用i指针遍历所有活动的开始时间。
    • 使用j指针遍历所有活动的结束时间。
    • 如果Start[i] >= End[j]，说明当前活动可以复用某个已结束的活动的主持人，j指针向前移动。
    • 如果Start[i] < End[j]，说明当前活动需要新增一名主持人。

  3. 计算结果：

    • 最终返回i - j，即需要的主持人数量。

复杂度分析

  • 时间复杂度：O(n log n)，主要由两次qsort排序操作决定。
  • 空间复杂度：O(n)，用于存储Start和End数组。

示例验证

详细分析例子5, [[1,3],[2,4],[2,8],[3,4],[4,10]]，并逐步解释代码是如何处理的。

输入数据
  • 活动数量：n = 5
  • 活动的开始时间和结束时间：
    [[1,3], [2,4], [2,8], [3,4], [4,10]]
代码执行过程
1. 提取并排序开始时间和结束时间

代码首先将所有活动的开始时间和结束时间分别提取到两个数组 Start 和 End 中，然后对这两个数组分别进行排序。

提取后的数组：

  • Start：[1, 2, 2, 3, 4]
  • End：[3, 4, 4, 8, 10]

排序后的数组：

  • Start：[1, 2, 2, 3, 4]（排序后不变）
  • End：[3, 4, 4, 8, 10]（排序后）
2. 双指针遍历

接下来，代码使用双指针 i 和 j 来判断哪些活动可以复用已有的主持人。

int i, j;
for (i = 1, j = 0; i < n; i++) {
    if (Start[i] >= End[j]) {
        j++;  // 如果当前活动的开始时间大于等于某个活动的结束时间，说明可以复用主持人
    }
}

双指针遍历过程：

  1. 初始状态：

    • i = 1，j = 0
    • Start[i] = 2，End[j] = 3
    • 2 < 3，说明活动 [2,4] 无法复用任何已结束的活动的主持人。

  2. 第二轮：

    • i = 2，j = 0
    • Start[i] = 2，End[j] = 3
    • 2 < 3，说明活动 [2,8] 也无法复用任何已结束的活动的主持人。

  3. 第三轮：

    • i = 3，j = 0
    • Start[i] = 3，End[j] = 3
    • 3 >= 3，说明活动 [3,4] 可以复用活动 [1,3] 的主持人，因此 j++。

  4. 第四轮：

    • i = 4，j = 1
    • Start[i] = 4，End[j] = 4
    • 4 >= 4，说明活动 [4,10] 可以复用活动 [2,4] 的主持人，因此 j++。

最终状态：

  • i = 5（遍历完所有活动）
  • j = 2（有两个活动可以复用已有的主持人）
3. 计算结果

最后，代码返回所需的主持人数量：

return i - j;  // i 是总活动数量，j 是可以复用的活动数量

计算结果：

  • i = 5（总活动数量）
  • j = 2（可以复用的活动数量）
  • 所需主持人数量 = 5 - 2 = 3

结论

对于输入 5, [[1,3],[2,4],[2,8],[3,4],[4,10]]，代码的输出是 3，表示需要 3名主持人 来成功举办所有活动。

验证

我们可以通过手动分析来验证这个结果：

  1. 活动 [1,3] 需要一个主持人。
  2. 活动 [2,4] 和 [2,8] 与 [1,3] 有时间冲突，因此需要两个新的主持人。
  3. 活动 [3,4] 可以复用 [1,3] 的主持人。
  4. 活动 [4,10] 可以复用 [2,4] 的主持人。

因此，总共需要 3名主持人，与代码的输出一致。


http://www.niftyadmin.cn/n/5864293.html

相关文章

MQTT实现智能家居------2、写MQTT程序的思路

MQTT实现智能家居------2、写MQTT程序的思路

举个最简单的例子&#xff1a; 手机------服务器-------家具 我们这里只看手机和家具的客户端&#xff1a; 手机&#xff1a;1&#xff09;需要连接服务器 2&#xff09;需要发布指令给服务器到家里的家具 3&#xff09;接受来自于家里家具的异常状况 4&#xff09;保持心…
阅读更多...
当“欲望号街车”遇阻：解锁自由的疯狂选择题

当“欲望号街车”遇阻：解锁自由的疯狂选择题

朋友们&#xff0c;今天咱来唠唠人生这出大戏里超烧脑的一幕&#xff1a;自由这玩意儿&#xff0c;据说等于能力减去欲望。啥意思呢&#xff1f;打个比方&#xff0c;你能力是10分&#xff0c;欲望却有20分&#xff0c;那自由值就是个负数&#xff0c;你得被折腾得死去活来&…
阅读更多...
Java 18~20 新特性

Java 18~20 新特性

文章目录 一、Java 18 新特性1.1、UTF-8 作为默认字符集&#xff08;JEP 400&#xff09;1.2、简易 Web 服务器&#xff08;JEP 408&#xff09;1.3、代码片段标签 snippet&#xff08;JEP 413&#xff09;1.4、使用方法句柄重新实现反射核心&#xff08;JEP 416&#xff09;1.…
阅读更多...
银河麒麟系统安装mysql5.7【亲测可行】

银河麒麟系统安装mysql5.7【亲测可行】

一、安装环境 cpu&#xff1a;I5-10代&#xff1b; 主板&#xff1a;华硕&#xff1b; OS&#xff1a;银河麒麟V10&#xff08;SP1&#xff09;未激活 架构&#xff1a;Linux 5.10.0-9-generic x86_64 GNU/Linux mysql版本&#xff1a;mysql-5.7.34-linux-glibc2.12-x86_64.ta…
阅读更多...
财务运营域——电子影像系统设计

财务运营域——电子影像系统设计

摘要 文章主要介绍了电子影像系统的设计与应用。随着企业规模扩大和业务复杂化&#xff0c;传统纸质文档管理方式暴露出诸多问题&#xff0c;电子影像技术应运而生。它通过数字化扫描、存储和管理纸质文档&#xff0c;实现高效检索、实时共享、安全存储和流程自动化&#xff0…
阅读更多...
机器学习数学通关指南——链式法则

机器学习数学通关指南——链式法则

前言 本文隶属于专栏《机器学习数学通关指南》&#xff0c;该专栏为笔者原创&#xff0c;引用请注明来源&#xff0c;不足和错误之处请在评论区帮忙指出&#xff0c;谢谢&#xff01; 本专栏目录结构和参考文献请见《机器学习数学通关指南》 正文 一、定义与公式 链式法则&a…
阅读更多...
DeepSeek 助力 Vue 开发：打造丝滑的单选按钮（Radio Button）

DeepSeek 助力 Vue 开发：打造丝滑的单选按钮（Radio Button）

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…
阅读更多...
基于Python和Neo4j开发的医疗辅助诊断系统的详细实现步骤和代码示例

基于Python和Neo4j开发的医疗辅助诊断系统的详细实现步骤和代码示例

以下是一个基于Python和Neo4j开发的医疗辅助诊断系统的详细实现步骤和代码示例。 1. 环境准备 首先&#xff0c;确保你已经安装了必要的库。可以使用以下命令进行安装&#xff1a; pip install py2neo2. Neo4j数据库初始化 在Neo4j中创建一个新的数据库&#xff0c;并启动N…
阅读更多...
最新文章

Copyright @ 2022~2023