文章目录

  • 一、题目介绍
  • 二、解题思路
    • 2.1 核心问题
    • 2.2 贪心策略
    • 2.3 正确性证明
  • 三、算法分析
    • 3.1 为什么按结束时间排序?
    • 3.2 复杂度分析
    • 3.3 算法流程图解
      • 3.3.1 流程图说明
      • 3.3.2 关键步骤说明
  • 四、模拟演练
  • 五、完整代码

一、题目介绍

在这里插入图片描述

  • 活动安排

题目描述
给定 nnn 个活动,每个活动的时间区间为 [ai,bi)[a_i, b_i)[ai,bi)(左闭右开)。要求选择尽可能多的活动,使得这些活动的时间区间互不重叠。

输入描述

  • 第一行:整数 nnn1≤n≤2×1051 \leq n \leq 2 \times 10^51n2×105),表示活动数量
  • 后续 nnn 行:每行两个整数 ai,bia_i, b_iai,bi0≤ai<bi≤1090 \leq a_i < b_i \leq 10^90ai<bi109

输出描述

  • 一个整数,表示最多可选择的活动数

示例

  • 输入:
    3
    1 4
    1 3
    3 5
    
  • 输出:2
  • 说明:可选择活动 [1,3)[1,3)[1,3)[3,5)[3,5)[3,5)

二、解题思路

2.1 核心问题

在多个时间区间中选出最大互斥子集——经典的区间调度问题

2.2 贪心策略

  1. 排序策略

    • 将所有活动按结束时间升序排序
    • 结束时间相同时,开始时间不影响结果(可任意排序)
  2. 选择策略

    • 初始化选择第一个活动(最早结束)
    • 遍历后续活动:
      • 若当前活动的开始时间 ≥\geq 上一个选中活动的结束时间
      • 则选择该活动,并更新记录点

2.3 正确性证明

  • 贪心选择性:最早结束的活动一定在某个最优解中
  • 最优子结构:选择最早结束活动后,剩余问题仍是相同结构的子问题
  • 反证法:若存在更优解,其第一个活动结束时间一定不早于贪心选择的活动

三、算法分析

3.1 为什么按结束时间排序?

排序方式反例问题原因
按开始时间排序
[1,5]
[2,3]
[4,6]
[1,5] 后无法选其他
按区间长度排序
[1,4]
[2,3]
[3,5]
选最短 [2,3] 后只能再选一个
按结束时间排序无反例保证最大化剩余时间

3.2 复杂度分析

  • 时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)
    • 排序:O(nlog⁡n)O(n \log n)O(nlogn)(占主导)
    • 遍历:O(n)O(n)O(n)
  • 空间复杂度O(n)O(n)O(n)
    • 存储 nnn 个活动对象

3.3 算法流程图解

flowchart TDA[开始] --> B[读取活动数量n]B --> C[创建空活动列表]C --> D[循环读取n个活动]D --> E[存储活动到列表]E --> F{是否读完n个活动?}F -- 否 --> DF -- 是 --> G[按结束时间升序排序]G --> H[初始化:count=0, lastEnd=-1]H --> I[遍历排序后活动列表]I --> J{当前活动开始时间 ≥ lastEnd?}J -- 是 --> K[count++,更新lastEnd=当前结束时间]J -- 否 --> L[跳过该活动]K --> M{是否还有活动?}L --> MM -- 是 --> IM -- 否 --> N[输出count]N --> O[结束]

在这里插入图片描述

3.3.1 流程图说明

  1. 数据读取阶段

    • 读取活动数量 n
    • 循环读取 n 个活动的时间区间
    • 存储在 ArrayList
  2. 排序阶段

    • 使用自定义比较器 ActivityComparator
    • 按结束时间升序排序(最早结束的在前)
  3. 贪心选择阶段

    flowchart LRP[lastEnd初始值-1] --> Q{遍历活动}Q --> R[活动A: start≥lastEnd?]R -- 是 --> S[选择A, count+1, lastEnd=A.end]R -- 否 --> T[跳过A]S --> U{继续遍历}T --> U
    

在这里插入图片描述

  1. 选择逻辑示例(输入 [[1,4], [1,3], [3,5]]):
    flowchart TBsubgraph 排序后A1[活动2: 1-3] --> A2[活动1: 1-4] --> A3[活动3: 3-5]endA1 --> B1{1 ≥ -1?} -- 是 --> C1[选择, count=1, lastEnd=3]C1 --> A2A2 --> B2{1 ≥ 3?} -- 否 --> C2[跳过]C2 --> A3A3 --> B3{3 ≥ 3?} -- 是 --> C3[选择, count=2, lastEnd=5]
    

在这里插入图片描述

3.3.2 关键步骤说明

  1. 排序意义

    • 结束时间最早的活动优先被选择
    • 为后续活动留下最大时间窗口
  2. lastEnd初始值-1的作用

    • 确保第一个活动总是被选择
    • 数学上满足:任意开始时间 ≥ -1
  3. 选择条件 start ≥ lastEnd

    • 严格保证活动时间不重叠
    • 充分利用左闭右开区间特性([1,3)[3,5) 可衔接)

此流程图清晰展示了贪心算法的核心思想:通过结束时间排序最大化剩余时间窗口,通过顺序遍历实现高效选择

四、模拟演练

输入数据

3
1 4
1 3
3 5

执行流程

  1. 排序阶段(按结束时间升序):

    原始顺序开始时间结束时间
    活动114
    活动213
    活动335

    ↓ 排序后 ↓

    新顺序开始时间结束时间
    活动213
    活动114
    活动335
  2. 选择阶段

    当前活动开始时间结束时间上一活动结束时间是否选择已选活动数更新结束时间
    活动213-1 (初始)13
    活动1143❌(1 < 3)13
    活动3353✅(3 ≥ 3)25
  3. 输出结果:2

边界测试

  • 全重叠活动
    输入:[1,2), [1,2), [1,2)
    输出:1(只能选一个)

  • 大范围数据
    输入:2×1052 \times 10^52×105[i,i+1)[i, i+1)[i,i+1) 区间
    输出:2×1052 \times 10^52×105(所有活动互不重叠)

五、完整代码

import java.util.*;/*** 活动类:表示一个活动的时间区间 [startTime, endTime)*/
class Activity {int startTime;  // 活动开始时间int endTime;    // 活动结束时间(不包含)// 构造函数Activity(int startTime, int endTime) {this.startTime = startTime;this.endTime = endTime;}
}/*** 活动比较器:按结束时间升序排序* 为什么按结束时间排序?因为结束时间决定了活动占用时间段的长度*/
class ActivityComparator implements Comparator<Activity> {@Overridepublic int compare(Activity a, Activity b) {// 按结束时间从小到大排序:最早结束的排前面return a.endTime - b.endTime;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 1. 读取活动数量int n = in.nextInt();// 2. 创建活动列表并存储所有活动List<Activity> activities = new ArrayList<>();for (int i = 0; i < n; i++) {int startTime = in.nextInt();int endTime = in.nextInt();activities.add(new Activity(startTime, endTime));}// 3. 关键步骤:按结束时间升序排序(贪心算法的核心)Collections.sort(activities, new ActivityComparator());// 4. 贪心选择过程int count = 0;          // 记录可安排的活动数量int lastEndTime = -1;   // 上一个被选中活动的结束时间(初始化为-1,表示尚未选择任何活动)for (Activity activity : activities) {// 如果当前活动开始时间 ≥ 上一个活动的结束时间(说明时间不重叠)if (activity.startTime >= lastEndTime) {count++;  // 选择不重叠的活动lastEndTime = activity.endTime;  // 更新最后一个活动的结束时间}}// 5. 输出结果System.out.println(count);}
}

关键优化点

  1. 结束时间排序
    Collections.sort(activities, (a, b) -> a.endTime - b.endTime);
    
  2. 贪心选择
    if (act.startTime >= lastEnd) {count++;lastEnd = act.endTime;
    }
    

为什么不用优先队列?

  • 排序后只需一次线性遍历,复杂度 O(n)O(n)O(n)
  • 优先队列 O(nlog⁡n)O(n \log n)O(nlogn) 的插入/删除反而增加开销

通过结束时间排序+贪心遍历,高效解决大规模区间调度问题

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/diannao/90491.shtml
繁体地址,请注明出处:http://hk.pswp.cn/diannao/90491.shtml
英文地址,请注明出处:http://en.pswp.cn/diannao/90491.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第1讲:C语言常见概念

目录 一、什么是C语言&#xff1f; 二、C语言的历史与成就 三、编译器选择&#xff08;VS2022&#xff09; 1、编译与链接 2、编译器对比 3、VS2022的优缺点 四、VS项目与源文件、头文件介绍 五、第一个C语言程序 六、main函数 七、printf和库函数 八、关键字介绍 …

WinUI3入门18:从APP打开商店链接以及实现内购

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 源码指引&#xff1a;github源…

BI布局拖拽 (1) 深入react-gird-layout源码

因为有个拖拉拽的需求&#xff0c;类似于quickBi那样的效果。在网上调研了一下发现react-grid-layout实现效果类似&#xff0c;但其也有局限性&#xff0c;比如不支持嵌套&#xff0c;不支持在多个gridLyaout之间互相拖拽。 要求&#xff1a;基于react-grid-layout的思路&#…

CentOS环境搭建-快速升级G++版本

在CentOS环境中快速升级G编译器版本&#xff0c;对于追求最新语言特性的开发者来说至关重要。由于CentOS默认的软件仓库可能不提供G的最新版本&#xff0c;我们通常需要借助第三方软件源&#xff0c;如Developer Toolset或使用Spack等包管理器来完成这一任务。下面将详细介绍两…

分布式接口幂等性的演进和最佳实践,含springBoot 实现(Java版本)

一、背景&#xff1a;为什么需要幂等性 在微服务、分布式架构下&#xff0c;网络不可靠、请求重试机制&#xff08;如前端超时重发、客户端重发、网关重试、消息消费失败重试等&#xff09;会带来重复请求&#xff0c;如果接口没有幂等性&#xff0c;可能导致&#xff1a; 重复…

OGRE 3D----6. 背景图片渲染实现详解

1. 背景图片渲染原理 1.1 渲染队列机制 Ogre3D 使用渲染队列(Render Queue)来控制对象的渲染顺序。背景图片需要在所有其他对象之前渲染,因此我们将其设置为 RENDER_QUEUE_BACKGROUND。 1.2 视图变换控制 为了让背景图片始终保持在场景的最远处,我们需要: 使用单位投影…

K线连续涨跌统计与分析工具

K线连续涨跌统计与分析工具 1. 概述 本工具是一个用于分析金融时间序列数据(特别是K线数据)的Python脚本,主要功能是统计连续n根同方向K线后,第n+1根K线的涨跌情况。该工具不仅提供统计分析功能,还支持图形化标记以验证结果,帮助交易者和量化分析师识别市场中的特定模式…

jQuery EasyUI 简介

jQuery EasyUI 简介 引言 随着互联网技术的飞速发展,前端开发变得越来越重要。jQuery EasyUI 作为一款流行的前端UI框架,极大地简化了前端开发的工作流程,提高了开发效率。本文将详细介绍 jQuery EasyUI 的起源、特点、使用方法以及在实际项目中的应用。 一、jQuery Easy…

《测试开发:从技术角度提升测试效率与质量》

测试开发的核心工作内容与职责解析 一、测试开发的定位与核心价值 测试开发&#xff08;Test Development&#xff0c;简称 TestDev 或 SDET&#xff09;是融合软件开发能力与测试工程思维的复合型岗位&#xff0c;不同于传统测试工程师&#xff0c;其核心目标是通过技术手段提…

20250710解决KickPi的K7开发板刷机之后出现DDR异常:ch:1 dq0 fail,write:0x1,read:0x20300

20250710解决KickPi的K7开发板刷机之后出现DDR异常&#xff1a;ch:1 dq0 fail,write:0x1,read:0x20300 2025/7/10 20:36[BEGIN] 2025/7/10 19:29:03 /DDR 2f85f4b2d4 cym 25/03/04-14:38.55,fwver: v1.09 In ch0 ttot10 ch0 ttot10 ch1 ttot10 ch0 ttot18 LPDDR4, 2112MHz chan…

Ansible:强大的自动部署工具

文章目录零、Ansible介绍一、安装 ansible二、配置SSH密钥1.检查密钥是否存在2.两边的机器要互相有对方的密钥三、自动部署1.传输文件(1)inventory.ini(2)sync_blt.yml(3)执行命令2.安装软件(1)inventory.ini(2)install_efvs.yml(3)执行命令零、Ansible介绍 Ansible 是一个开源…

Nacos的基本功能以及使用Feign进行微服务间的通信

Nacos是Dynamic Naming and Configuration Service的缩写。What’s Nacos? 下面结合SpringBoot项目&#xff0c;为你介绍Nacos的基本功能以及如何使用Feign进行微服务间的通信。 一、Nacos的基本功能 Nacos是阿里巴巴开源的一个更易于构建云原生应用的动态服务发现、配置管…

C1编译器和C2编译器Test01

在HotSpot VM中内嵌有两个JIT编译器&#xff0c;分别为Client Compiler和Server Compiler&#xff0c;通常简称为C1编译器和C2编译器。开发人员可以通过如下命令显式指定JVM在运行时到底使用哪一种即时编译器。(1)-client&#xff1a;指定JVM运行在Client模式下&#xff0c;并使…

MongoDB与Spring Boot完整使用指南

目录 1. MongoDB基础概念 什么是MongoDB? 核心概念对比 文档结构示例 2. MongoDB的特点与优势 主要特点 适用场景 3. MongoDB基本操作 基本CRUD操作 插入文档 查询文档 更新文档 删除文档 4. Spring Boot集成MongoDB 步骤1:添加依赖 步骤2:配置数据库连接 …

swift开发,关于应用、页面、视图的生命周期

目录一、应用生命周期&#xff08;App Lifecycle&#xff09;UIKit (AppDelegate)SwiftUI (使用 ScenePhase)二、页面生命周期&#xff08;ViewController Lifecycle&#xff09;三、视图生命周期&#xff08;UIView Lifecycle&#xff09;四、SwiftUI 视图生命周期五、关键对比…

借助HarmonyOS SDK,《NBA巅峰对决》实现“分钟级启动”到“秒级进场”

《NBA巅峰对决》是由望尘科技推出的国内首个真实还原5V5王朝模式的操作篮球手游&#xff0c;提供流畅操作手感和真实篮球赛场体验。丰富的玩法在为玩家带来高质游戏体验的同时&#xff0c;间接带来了启动流程冗长的问题&#xff0c;资源更新阶段的等待感尤为突出。 “我们发现&…

HT-LINK ICE:海速芯32Gbps信号调理芯片,40dB补偿+国产自主,打破高速互联瓶颈!

HT-LINK ICE&#xff08;TENX海速芯&#xff09;产品解析与推广文案一、产品定位HT-LINK ICE是TENX海速芯推出的高速信号调理芯片&#xff0c;专为PCIe 5.0/6.0、USB4、Thunderbolt等超高速接口设计&#xff0c;提供信号完整性增强和时钟恢复功能&#xff0c;适用于数据中心、A…

深入剖析 ADL:C++ 中的依赖查找机制及其编译错误案例分析

一、ADL 的定义与背景&#xff08;一&#xff09;ADL 的定义ADL&#xff08;Argument-Dependent Lookup&#xff0c;依赖查找&#xff09;是 C 中一种特殊的名称查找机制&#xff0c;用于在调用函数时&#xff0c;根据函数参数的类型来确定查找的命名空间范围。ADL 的核心思想是…

【科研绘图系列】R语言绘制相关系数图

文章目录 介绍加载R包数据下载导入数据数据预处理画图系统信息参考介绍 【科研绘图系列】R语言绘制相关系数图 加载R包 library(vegan) library(dplyr)# install.packages("./RVisulizationData/003.mantel test/ggcor_0.9.8.1.tar.gz", repos = NULL, type = &quo…

pharokka phold--快速噬菌体注释工具

pharokka是一款专用于噬菌体基因组及宏基因组的快速标准化注释工具。PS.仍在积极更新中&#xff0c;最近一次更新是在今年6.20。 若需对细菌基因组进行快速标准化注释&#xff0c;建议使用Bakta。启发pharokka开发及命名的Prokka也是优秀选择&#xff0c;但Bakta实为Prokka的卓…