当前位置： 首页 > news >正文

【蓝桥杯】贪心算法

news 来源：原创 2025/9/17 2:18:35

1. 区间调度

1.1. 题目

给定n个区间，每个区间由开始时间start和结束时间end表示。请选择最多的互不重叠的区间，返回可以选择的区间的最大数量。

输入格式：

  • 第一行包含一个整数n，表示区间的数量

  • 接下来n行，每行包含两个整数，分别表示区间的开始时间和结束时间

输出格式：

  • 一个整数，表示最多可以选择的互不重叠的区间数量

示例输入：

4
1 3
2 4
3 5
6 7

示例输出：

3

1.2. 思路

1. 理解问题：我们需要从给定的多个区间中选出尽可能多的区间，且这些区间之间没有任何重叠部分。

2. 贪心算法思想：贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望导致全局最优的结果。对于区间调度问题，常见的贪心策略有：

  • 最早开始时间

  • 最早结束时间

  • 最短区间长度

  • 最少冲突区间

其中，"最早结束时间"策略被证明可以得到最优解。

3. 为什么选择最早结束时间？

  • 选择一个结束早的区间，可以给后面留下更多的时间安排其他区间

  • 这样能最大化剩余可用时间，从而可能选择更多区间

4. 算法步骤

  1. 将所有区间按照结束时间从小到大排序

  2. 初始化选择的区间数量为0，记录上一个选中区间的结束时间

  3. 遍历排序后的区间：

    • 如果当前区间的开始时间 >= 上一个选中区间的结束时间

    • 则选择当前区间，更新结束时间，计数+1

  4. 返回最终的计数结果

5. 时间复杂度

  • 排序：O(n log n)

  • 遍历：O(n)

  • 总时间复杂度：O(n log n)

1.3. 代码

# 读取输入
n = int(input())  # 区间数量
intervals = []
for _ in range(n):start, end = map(int, input().split())intervals.append([start, end])"""
计算最多可以选择的互不重叠的区间数量  
参数:intervals: 区间列表，每个区间表示为[start, end]  
返回:最多可以选择的互不重叠的区间数量
"""
# 特殊情况处理：如果没有区间或只有一个区间
if not intervals:print(0)
if len(intervals) == 1:print(1)
# 1. 按照区间的结束时间进行升序排序
# 这样我们可以优先选择结束早的区间

相关文章：

【蓝桥杯】贪心算法

1. 区间调度 1.1. 题目 给定个区间，每个区间由开始时间start和结束时间end表示。请选择最多的互不重叠的区间，返回可以选择的区间的最大数量。 输入格式： 第一行包含一个整数n，表示区间的数量 接下来n行，每行包含两个整数，分别表示区间的开始时间和结束时间 输出格式：…...

编程日记 2025/9/17 2:18:35

从一批视频里面抽取固定的第n帧图片（包含并行实现）

以下代码主要用于从 ./*.mp4 的文件夹中，每个视频中抽取第N帧保存成图，用于图生视频训练，考虑到数据量比较大，推荐使用ffmpeg来实现的，性能可以比较高（10w个视频差不多十多分钟就可以跑完）&…...

编程日记 2025/9/17 2:12:29

论文阅读：2024-arxiv How to Steer LLM Latents for Hallucination Detection?

总目录 大模型安全相关研究：https://blog.csdn.net/WhiffeYF/article/details/142132328 How to Steer LLM Latents for Hallucination Detection? https://arxiv.org/pdf/2503.01917 https://www.doubao.com/chat/2818934852496130 其它资料： http…...

编程日记 2025/9/9 10:00:47

python面试技巧

文章目录 前言面试前面试中良好的沟通表达展示解决问题的能力体现学习能力和热情注意非语言沟通 面试后 前言 在 Python 面试中，掌握一些有效的技巧能让你更好地展现自己的能力和素质，以下是一些实用的面试技巧： 面试前 研究公司和岗位&…...

编程日记 2025/9/12 8:04:12

免费AI编程插件Fitten Code + IntelliJ IDEA实现AI辅助编程实战指南

🧑 博主简介：CSDN博客专家、CSDN平台优质创作者，高级开发工程师，数学专业，拥有高级工程师证书；擅长C/C、C#等开发语言，熟悉Java常用开发技术，能熟练应用常用数据库SQL server,Oracle…...

编程日记 2025/9/17 2:12:56

Vue3 + TypeScript 的 Hooks 实用示例

示例 1: 防抖 Hook（useDebounce） typescript // hooks/useDebounce.ts import { ref, watch, onUnmounted, type WatchSource } from vue;/*** 防抖 Hook* param source 监听的响应式数据源* param callback 防抖后执行的回调函数* param delay 防抖延…...

编程日记 2025/9/15 1:37:56

【DB2】事务日志满/归档占用较大问题处理记录

某DB2环境经常报错The active log is full and is held by...，并且归档磁盘占用较大 事务日志满 事务日志满可以理解为Oracle的redo追尾，即业务写入量大于redo刷盘速度，这时候其他SQL会陷入等待，容易造成性能问题 一般由两方面原…...

编程日记 2025/9/16 7:15:06

Rust 的征服：从系统编程到全栈开发的 IT 新宠

文章目录 Rust 的本质：性能与安全的完美平衡Rust 的演进：从 Mozilla 的实验到全球热潮核心技术：Rust 的杀手锏与生态所有权与生命周期高并发：无畏线程Cargo：现代构建工具生态繁荣：Crates.io Rust 的杀手级应…...

编程日记 2025/9/17 2:15:10

【力扣hot100题】（086）乘积最大子数组

感觉题目越来越难，这题不看答案真的想不到一点。 一开始绕了不少弯路，甚至想将每一个子数组的积全部求出来比较…… 答案的方法有点难懂。 方法如下：维护两个数，分别是目前为止最大数和最小数，最大数一般来说是正数…...

编程日记 2025/9/16 7:13:53

编译器bug ?

## 问题描述 两个结构几乎相同的模板实现&#xff0c;一个能正常工作&#xff0c;另一个在 VS2019 和 GCC 中都会报错。 ## 最小化测试代码 // bug_report.cpp #include <type_traits> #include <string>template<typename T> struct Type2Type { using t…...

编程日记 2025/9/17 2:17:58

算法刷题记录——LeetCode篇(1.8) [第71~80题](持续更新)

更新时间&#xff1a;2025-04-10 算法题解目录汇总&#xff1a;算法刷题记录——题解目录汇总技术博客总目录&#xff1a;计算机技术系列博客——目录页 优先整理热门100及面试150&#xff0c;不定期持续更新&#xff0c;欢迎关注&#xff01; 72. 编辑距离 给你两个单词 wo…...

编程日记 2025/9/17 2:15:08

leetcode68.左右文本对齐

思路源自 leetcode-字符串篇 68题 文本左右对齐 难度高的模拟类型题目&#xff0c;关键点在于事先知道有多少单词要放在本行并且还要知道本行是不是最后一行&#xff08;最后一行需要全部单空格右对齐&#xff0c;不是最后一行就空格均摊&#xff09;&#xff0c;非最后一行的空…...

编程日记 2025/9/11 4:22:42

leetcode:905. 按奇偶排序数组（python3解法）

难度&#xff1a;简单 给你一个整数数组 nums&#xff0c;将 nums 中的的所有偶数元素移动到数组的前面&#xff0c;后跟所有奇数元素。 返回满足此条件的 任一数组 作为答案。 示例 1&#xff1a; 输入&#xff1a;nums [3,1,2,4] 输出&#xff1a;[2,4,3,1] 解释&#xff1a…...

编程日记 2025/9/17 2:15:43

Java抽象类与抽象方法详解

一、抽象类的作用与定义 1. 核心作用 ​​设计意图​​&#xff1a;当多个子类具有共性行为但具体实现不同时&#xff0c;通过抽象类强制规范子类的实现格式。 ​​典型场景​​&#xff1a; // 定义抽象图形类 public abstract class Shape {// 抽象方法&#xff1a;计算面…...

编程日记 2025/9/15 17:21:35

QScrCpy源码解析（3）监听手机usb端口

采用的技术方式为adb adb可以通过命令行达到控制安卓手机的目的 大致思路为 1在界面显示的时候初始化一个定时器&#xff0c;不断地查询当前设备连接到的手机安卓设备 使用的adb指令为 adb devices 定时器代码 connect(&m_autoUpdatetimer, &QTimer::timeout, th…...

编程日记 2025/9/9 0:46:41

go-zero学习笔记（六）---gozero中间件介绍

​ 1. 中间件分类 gozero默认中间件通过在api文件中创建的中间件通过server.Use(middleware Middleware)创建的中间件2. 中间件介绍 2.1 gozero默认中间件 默认中间件包括如下&#xff1a;在gozero中对应的代码为&#xff1a; // 文件位置&#xff1a;github.com\zeromicro\g…...

编程日记 2025/9/17 2:15:09

基于FPGA实现BPSK 调制

目录 一、 任务介绍二、基本原理三、基于FPGA实现BPSK 调制四、源码 一、 任务介绍 BPSK 调制在数字通信系统中是一种极重要的调制方式&#xff0c;它的抗干扰噪声性能及通频带的利用率均优先于 ASK 移幅键控和 FSK 移频键控。因此&#xff0c;PSK 技术在中、高速数据传输中得…...

编程日记 2025/9/17 2:15:08

包含网络、平台、数据及安全四大体系的智慧快消开源了

智慧快消视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。国产化人工智能“…...

编程日记 2025/9/17 2:14:41

基于AWS的大模型调用场景：10大成本优化实战方案

大模型训练与推理是AI领域的计算密集型场景&#xff0c;如何在AWS上实现高性能与低成本的双重目标&#xff1f;本文从实例选型、弹性伸缩、存储优化等角度&#xff0c;分享10个经过验证的AWS成本优化策略&#xff0c;帮助企业节省30%以上成本。 一、大模型场景的成本痛点分析 计…...

编程日记 2025/9/17 2:17:58

Human3.6M 解析3d pose标注 h36m

目录 解析pkl 并可视化 解析h5格式： view_h36m_h5_ok.py nlf 预测并计算指标mpje 解析pkl 并可视化 import os import pickleimport cv2 import imageio import numpy as npif __name__ == __main__:# pkl_path=r"E:\data\pose_3d\human3.6mtoolbox\annot\h36m_valid…...

编程日记 2025/9/17 2:17:57

设计模式-观察者模式和发布订阅模式区别

文章目录 其他不错的文章 二者有类似的地方&#xff0c;也有区别。 引用的文章说的已经比较清楚了&#xff0c;这里只列出对比图。 对比点观察者模式发布订阅模式中间人角色无事件中心&#xff0c;观察者直接订阅目标有事件中心&#xff0c;发布者与订阅者通过事件中心通信关系…...

编程日记 2025/9/11 8:25:49

Python proteinflow 库介绍

ProteinFlow是一个开源的Python库，旨在简化蛋白质结构数据在深度学习应用中的预处理过程。以下是其详细介绍： 功能 数据处理：支持处理单链和多链蛋白质结构，包括二级结构特征、扭转角等特征化选项。 数据获取：能够从Protein Data Bank (PDB)和Structural Antibody Databa…...

编程日记 2025/9/11 14:06:08

羽绒服选购

羽绒服怎么选&#xff1f; 看吊牌 填充物含绒子量充绒克数 填充物&#xff1a; 鹅绒>鸭绒>鹅鸭混合绒 中国90%羽绒服都是鸭绒&#xff0c;鹅绒产量少&#xff0c;且拔毛方式不人道&#xff0c;所以价格更高 白鸭绒和黑鸭绒区别不大&#xff0c;但是白羽绒服只能用白鸭绒…...

编程日记 2025/9/15 3:18:50

使用注解@RequestBody变红的解决问题

解决办法&#xff1a; package com.takeout.controller;import com.takeout.common.R; import com.takeout.entity.Employee; import com.takeout.service.EmployeeService; import lombok.extern.slf4j.Slf4j; import org.springframework.beans.factory.annotation.Autowire…...

编程日记 2025/9/13 20:57:01

Multi-Agent Routing Value Iteration Network(多智能体路由值迭代网络)论文阅读

标题&#xff1a;Multi-Agent Routing Value Iteration Network(多智能体路由值迭代网络) 作者&#xff1a;Quinlan Sykora&#xff0c; Mengye Ren&#xff0c; Raquel Urtasun 单位: Uber 发表期刊&#xff1a;AI 发表时间&#xff1a;2020年 论文研究主题归类&#xf…...

编程日记 2025/9/9 15:48:05

商品详情 API 返回数据字段说明

京东商品详情 API 返回的数据是一个结构化的 JSON 对象&#xff0c;包含了商品的多个关键字段。以下是一些常见的返回值字段及其说明&#xff1a; 1. 商品基本信息 num_iid&#xff1a;商品唯一标识符。 title&#xff1a;商品标题。 desc_short&#xff1a;商品简短描述。 …...

编程日记 2025/9/12 12:56:22

数据结构 | 证明链表环结构是否存在

❤个人主页&#xff1a; 链表环结构 0.前言1.环形链表&#xff08;基础&#xff09;2.环形链表Ⅱ&#xff08;中等&#xff09;3.证明相遇条件及结论3.1 问题1特殊情况证明3.2 问题1普适性证明 0.前言 在这篇博客中&#xff0c;我们将深入探讨链表环结构的检测方法&#xff1a;…...

编程日记 2025/9/11 7:35:52

AI Agent类开发应避免Python独舞，奏响多技术交响曲

、 &#xff08;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff09;。 一、Python的局限&#xff1a;从“万能”到“单薄”的技术困境 1.1 Python的统治地位与暗礁 Python在AI…...

编程日记 2025/9/11 6:28:02

git基本使用

git 默认情况下&#xff0c;克隆的远程仓库会被命名为 origin git remote remove origin # 移除默认的远程仓库 origingit remote add origin https://github.com/CS144/minnow.git # 添加一个新的远程仓库 origin&#xff0c;指向自己的 GitHub 仓库git branch -M main #将当…...

编程日记 2025/9/13 1:25:19

解决IDEA中自动生成返回值带final修饰的问题

修改配置文件&#xff1a; 1、在settings选项下&#xff0c;Editor–Code Style–Java–Code Generation&#xff0c;确保红框内的两项不被勾选 2、在自动生成的地方,仔细观看final下面带有下划线,说明此处存在快捷键,这时按下ALT F, 选项框会取消勾选Declare final. 回车接…...

编程日记 2025/9/6 0:22:12

Java中的Exception和Error有什么区别？还有更多扩展

概念 在Java中&#xff0c;Exception和Error都是Throwable的子类&#xff0c;用于处理程序中的错误和异常情况。 然而&#xff0c;它们在用途和处理方式上有显著的不同&#xff1a; Exception&#xff1a; 用于表示程序在正常运行过程中可能出现的错误&#xff0c;如文件未找…...

编程日记 2025/9/10 7:28:00

什么是中性线、零线、地线，三相四线制如何入户用电

在变压器三相电侧&#xff0c;按照星形连接法&#xff0c;有一个中心点&#xff0c;这根线引出来的线接不接地&#xff1a;不接地就是中性线&#xff0c;接地就是零线 下面就是没有接地&#xff1a;中性线 接地了以后就可以叫做零线了 三相电在高压输电的时候是没有零线的&a…...

编程日记 2025/9/16 4:45:42

不用额外下载jar包，idea快速查看使用的组件源码

以nacos为例子&#xff0c;在idea中引入了nacos依赖&#xff0c;就可以查看源码了。 2. idea选择open&#xff08;不关闭项目直接选择file-open也可以&#xff09;, 在maven的仓库里找到对应的包&#xff0c;打开 2.idea中选择 jar包&#xff0c;选择 add as library 3.这样j…...

编程日记 2025/9/8 19:26:21

Ant Design X 和 Element-Plus-X

Ant Design X 是 Ant Design 的全新 AGI 组件库&#xff0c;旨在帮助开发者更轻松地研发 AI 产品用户界面。提供AI交互所需的Attachments、Sender、ThoughtChain等组件&#xff0c;以及useXAgent、XStream等hooks。 具备支持Vue和React两个版本 React&#xff1a; https://gi…...

编程日记 2025/9/16 1:57:44

jetson配置yolov5(tensor加速版）出现的问题（killed+tensor+~)

1.在cmake生成engine引擎文件时&#xff0c;出现一系列报错 make [ 20%] Building NVCC (Device) object CMakeFiles/myplugins.dir/myplugins_generated_yololayer.cu.o /home/lin/yolov5-4.0/yolov5/yololayer.h(54): error: member function declared with "override&…...

编程日记 2025/9/4 19:20:24

【华为战报】2025年3月 考试战报！

原创&#xff1a;厦门微思网络 了解更多往期考试→点 【考试战报】 华为认证 HCIA 3月 微思 | HCIA 考试战报 学员成绩单 华为认证 HCIP 3月 微思 | HCIP 考试战报 学员成绩单 学员证书 华为认证 HCIE 3月 微思 | HCIE 考试战报 学员成绩单 学员证书 华为认证 最新开班 厦门面授…...

编程日记 2025/9/14 14:58:56

daz3d ERC Freeze to Morph Target 和 另存为 Morph Asset(s)

. ERC 冻结至变形目标 (ERC Freeze to Morph Target) 核心目标&#xff1a;将骨架的调整与自定义造型的滑块关联起来。 详细解释&#xff1a; 当你创建一个自定义造型&#xff08;Morph&#xff09;并调整了骨架&#xff08;Rigging&#xff09;以适应这个新造型后&#xff…...

编程日记 2025/9/15 10:27:28

【网络安全 | 项目开发】Web 安全响应头扫描器（提升网站安全性）

未经许可，不得转载。 文章目录 项目简介项目功能示例输出技术栈：简单代码结构可选扩展功能项目简介 Web 安全响应头扫描器（Security Headers Checker），一个安全合规工具，用于检测目标网站是否配置了关键的 HTTP 安全头部，帮助开发者提升网站基础安全性。 项目功能 1.…...

编程日记 2025/9/2 18:28:21

Python - 爬虫-网页抓取数据-库requests

requests库是一个功能强大的HTTP库&#xff0c;用于发送各种HTTP请求&#xff0c;如GET、POST、PUT、DELETE等。 requests官网&#xff1a;Requests: HTTP for Humans™ — Requests 2.32.3 documentation 使用requests可以模拟浏览器的请求&#xff0c;比起之前用的urllib&a…...

编程日记 2025/9/6 22:42:45

antv x6使用（支持节点排序、新增节点、编辑节点、删除节点、选中节点）

项目需要实现如下效果流程图&#xff0c;功能包括节点排序、新增节点、编辑节点、删除节点、选中节点等 html部分如下&#xff1a; <template><div class"MindMapContent"><el-button size"small" click"addNode">新增节点&…...

编程日记 2025/9/13 9:14:30

Nginx 是什么？Nginx高并发架构拆解指南

你是一个程序员&#xff0c;你在电脑上编辑了一段文本&#xff0c;将它保存为 txt 文件。将它拖到浏览器打开&#xff0c;就能看到文件里的内容。 但这看起来太过单调&#xff0c;为了让画面更丰富&#xff0c;我们定个规则&#xff0c;在文本边上加个两个h1符号&#xff0c;文…...

编程日记 2025/9/12 12:48:04

JS forEach方法

遍历数组...

编程日记 2025/9/2 15:04:07

可道云支持群晖的docker安装了:全网唯一支持onlyoffice安装说明

在群晖系统上部署可道云面临显著的技术门槛。DSM7.2版本因不兼容Apache2.2等组件&#xff0c;用户需改用Docker手动配置环境&#xff0c;涉及PHP扩展、SQLite3适配及存储路径映射等复杂操作&#xff0c;且安装后需通过WebStation调整脚本语言参数&#xff0c;对非专业用户极不友…...

编程日记 2025/9/11 10:05:26

V4L2杂谈

V4L2的开发手册 在做v4l2的开发的时候&#xff0c; 可以使用v4l2-ctl命令协助调试和软件开发。关于linux多媒体开发可以参考链接&#xff1a;https://www.linuxtv.org/wiki/index.php/Main_Page关于v4l2的api接口开发可以参考&#xff1a;https://linuxtv.org/docs.php在linux…...

编程日记 2025/9/14 3:19:07

Java—HTML:3D形变

今天我要介绍的是在Java HTML中CSS的相关知识点内容之一&#xff1a;3D形变&#xff08;3D变换&#xff09;。该内容包含透视&#xff08;属性&#xff1a;perspective&#xff09;&#xff0c;3D变换&#xff0c;3D变换函数以及案例演示&#xff0c; 接下来我将逐一介绍&…...

编程日记 2025/9/16 3:22:54

Zotero PDF Translate 翻译插件使用OpenAI API配置教程

PDF Translate&#xff1a;提升 Zotero 内置 PDF 阅读器的翻译功能 “PDF Translate” 是一款为 Zotero 设计的插件&#xff0c;旨在方便用户在 Zotero 内置的 PDF 阅读器中进行划词或段落翻译&#xff0c;辅助阅读外文文献。 一、 安装插件 下载插件&#xff1a; 访问 PDF T…...

编程日记 2025/9/11 11:31:07

[raspberrypi 0w and respeaker 2mic]实时音频波形

0. 环境 ubuntu22主机&#xff0c; 192.168.8.162&#xff0c; raspberry 0w&#xff0c; 192.168.8.220 路由器 1. 树莓派 # rpi - send.py # 或者命令行&#xff1a;arecord -D plughw:1,0 -t wav -f cd -r 16000 -c 2 | nc 192.168.8.162 12345import socket imp…...

编程日记 2025/9/11 7:08:47

go-zero自动生成repository文件和测试用例

文章目录 repository的作用自动生成repository文件repo模板文件repo_test模板文件生成结果运行测试用例 repository的作用 在软件开发中&#xff0c;尤其是在采用分层架构或者领域驱动设计&#xff08;DDD&#xff09;的项目里&#xff0c;repository&#xff08;仓库&#xf…...

编程日记 2025/9/16 20:28:46

红宝书第三十六讲：持续集成（CI）配置入门指南

红宝书第三十六讲&#xff1a;持续集成&#xff08;CI&#xff09;配置入门指南 资料取自《JavaScript高级程序设计&#xff08;第5版&#xff09;》。 查看总目录&#xff1a;红宝书学习大纲 一、什么是持续集成&#xff1f; 持续集成&#xff08;CI&#xff09;就像咖啡厅的…...

编程日记 2025/9/16 8:29:00

【Java学习】如何利用AI学习Java语言开发（二）

利用AI辅助学习Java语言开发可以显著提高学习效率、解决实际问题和优化代码质量。以下是结合AI工具和方法的系统化学习路径： 一、AI辅助学习基础阶段 智能交互式学习平台 使用Codecademy（AI驱动版）或JetBrains Academy的Java课程，AI会根据你的代码实时提供修正建议 尝试Ch…...

编程日记 2025/9/10 19:34:41