630. 课程表 III

文章目录

  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:贪心+优先队列
  • 写在最后

Tag

【贪心】【优先队列】【数组】


题目来源

630. 课程表 III


题目解读

n 门编号从 1n 的课程,有一个数组 courses,其中 courses[i] = [duration, lastDay] 表示第 i 门课将会持续上 duaration 天,并且必须在 lastDay 之前完成(包括这一天)。你的学期从第一天开始,且不能同时上两门及以上的课程,返回你最多可以修完多少门课程。


解题思路

方法一:贪心+优先队列

为了尽可能多的学习课程,我们优先学习 lastDay 靠前的课程。如果当前课程的结束时间和 lastDay 有冲突了,并且前面学习过的课程中持续时间最长的课程持续时间大于当前课程,就用当前课程替换掉学习过的课程中持续时间最长的课程。

具体地,首先需要对 courses 课程进行按照 lastDay 字段进行升序排序;接着维护一个优先队列 q 用来存放可以学习的课程,如果遇到冲突,直接 q.top() 取出的就是学习过的课程中持续时间最长的课程,如果学习过的课程中持续时间最长的课程的持续时间大于当前课程的持续时间,则用当前课程的持续时间替换之。最后返回 q 的长度即为可以学习的课程数量的最大值。

实现代码

class Solution {
public:int scheduleCourse(vector<vector<int>>& courses) {sort(courses.begin(), courses.end(), [](const auto& c1, const auto& c2) {return c1[1] < c2[1];  });priority_queue<int> q;int total = 0;      // 学习过课程的总时间节点for (const auto& course : courses) {int t = course[0], d = course[1];if (total + t <= d) {total += t;q.push(t);}else if (!q.empty() && q.top() > t) {total -= q.top();total += t;q.pop();q.push(t);}}return q.size();}
};

复杂度分析

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),排序需要的时间为 O ( n l o g n ) O(nlogn) O(nlogn)。优先队列单次需要 O ( l o g n ) O(logn) O(logn) 的时间,每个课程最多被取出或放入队列一次,因此时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

空间复杂度: O ( n ) O(n) O(n),是优先队列需要使用的空间。


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

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

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

相关文章

idea报错“Static methods in interface require -target:jvm-1.8”

如题&#xff0c;在 idea 中跑 java 、scala 混编代码时&#xff0c;出现上面的错误。 问题的原因很明显是 idea 中的 jdk 版本设置有问题&#xff0c;针对性作如下排查&#xff1a; 检查项目的 java 版本 在File-> Project Settings中&#xff0c;检查检查idea的 java 版本…

【数据结构】树和二叉树概念

1.树概念及结构 树概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 有一个特殊的结点&#xff0c;…

EditPlus 配置python 及Anaconda中的python

若不是pycharm vscode 太大&#xff0c;太占内存&#xff0c;谁会想到用Notepad&#xff0c;EdirPlus 配置python呢&#xff01;&#xff01;&#xff01; 话不多说&#xff0c;首先你自己安装好EditPlus。开始 菜单栏 选择 工具 -> 配置自定义工具 组名:python 命令:d:\*…

组件间方法传递和响应(重要)

1、子组件通知父组件某时执行父组件的函数 父组件 当子组件emit时&#xff0c;父组件clickEven函数就执行了 子组件 ——————————————————————————————————————————— 2、父组件通知子组件某时执行自己的一个函数 父组件 一定要有…

Java 多线程系列Ⅶ(线程安全集合类)

线程安全集合类 前言一、多线程使用线性表二、多线程使用栈和队列三、多线程下使用哈希表 前言 在数据结构中&#xff0c;我们学习过 Java 的内置集合&#xff0c;但是我们知道&#xff0c;我们学过的大多数集合类都是线程不安全的&#xff0c;少数如 Vector&#xff0c;Stack…

【基础计算机网络1】认识计算机网络体系结构,了解计算机网络的大致模型(下)

前言 在上一篇我们主要介绍了有关计算机网络概述的内容&#xff0c;下面这一篇我们将来介绍有关计算机网络体系结构与参考模型的内容。这一篇博客紧紧联系上一篇博客。 这一篇博客主要内容是&#xff1a;计算机网络体系结构与参考模型&#xff0c;主要是计算机网络分层结构、协…

easypoi和poi版本兼容问题记录

最近在开发导出word的功能&#xff0c;遇到下面的问题 提示xml报错的问题&#xff0c;我一度以为是项目换了java11造成的。经过询问朋友&#xff0c;得知有可能是版本冲突造成的&#xff0c;就猛然想起来&#xff0c;我的项目里面还引入了poi这个包。 于是我吧poi的版本降低到了…

从零开发一款ChatGPT VSCode插件

‍本文作者是360奇舞团开发工程师 引言 OpenAI发布了ChatGPT&#xff0c;就像是给平静许久的互联网湖面上扔了一颗重磅炸弹&#xff0c;刹那间所有人都在追捧学习它。究其原因&#xff0c;它其实是一款真正意义上的人工智能对话机器人。它使用了深度学习技术&#xff0c;通过大…

【源码】JavaWeb+Mysql招聘管理系统 课设

简介 用idea和eclipse都可以&#xff0c;数据库是mysql&#xff0c;这是一个Java和mysql做的web系统&#xff0c;用于期末课设作业 cout<<"如果需要的小伙伴可以http://www.codeying.top";可定做课设 线上招聘平台整合了各种就业指导资源&#xff0c;通过了…

PCL入门(一):ubuntu20使用apt安装pcl

目录 0. 背景1. apt安装的版本2. 更新apt源3. apt安装命令4. 测试 0. 背景 使用源码安装pcl较为麻烦&#xff0c;因为存在依赖库vtk&#xff0c;flann&#xff0c;boost&#xff0c;eigen等&#xff0c;都不太好安装&#xff0c;因此采用apt方式安装。 下面内容主要参考博客《…

Redis之string类型的三大编码解读

目录 string类型的三大编码 int 编码 embstr 编码 raw 编码 明明没有超过阈值,为什么变成raw&#xff1f; 查看数据类型相关命令 redis看看类型:type key 看看编码:object encoding debug结构:debug object person 在 Redis 中&#xff0c;String 类型的数据结构并…

【linux基础(五)】Linux中的开发工具(上)---yum和vim

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:Linux从入门到开通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学更多操作系统知识   &#x1f51d;&#x1f51d; Linux中的开发工具 1. 前言2.…

让照片动起来的软件,轻松制作照片动效

随着社交媒体的日益普及&#xff0c;我们对于照片的要求也越来越高。普通的照片已经不能满足我们的需求&#xff0c;我们希望照片更加生动有趣。照片动效便应运而生&#xff0c;它可以让照片动起来&#xff0c;吸引更多的注意力&#xff0c;让照片更加生动有趣。 照片动效制作起…

C盘清理教程

C盘清理教程 首先使用space Sniffer 扫一下c盘&#xff0c;然后看一下到底是哪个文件这么大 第二步&#xff0c;创建软链接。 首先将我们需要移动的文件的当前路径拷贝下来&#xff1a;C:\Users\Tom\Desktop\test-link\abc\ghi.txt 然后假设剪切到D盘下&#xff1a;D:\ghi.…

颜色代码对照表

颜色代码对照表 各颜色代码: 1 白色 #FFFFFF 2 红色 #FF0000 3 绿色 #00FF00 4 蓝色 #0000FF 5 牡丹红 #FF00FF 6 青色 #00FFFF 7 黄色 #FFFF00 8 黑色 #000000 9 海蓝 #70DB93 …

FPGA原理与结构——时钟IP核的使用与测试

一、前言 本文介绍xilinx的时钟IP核 Clocking Wizard v6.0的具体使用与测试过程&#xff0c;在学习一个IP核的使用之前&#xff0c;首先需要对于IP核的具体参数和原理有一个基本的了解&#xff0c;具体可以参考&#xff1a; FPGA原理与结构——时钟IP核原理学习https://blog.c…

用于非线性多载波卫星信道的多输入多输出符号速率信号数字预失真器DPD(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Docker使用及本地Yolov5打包教程

1. Docker的安装 注意&#xff1a;官方也提供了直接Pull Yolov5的渠道&#xff1a; docker pull ultralytics/yolov5 详见&#xff1a;https://hub.docker.com/r/ultralytics/yolov5 --------------------------------------------------以下正文------------------------…

SOC 2.0安全运营中心

SOC&#xff0c;安全运营中心&#xff0c;为取得其最佳效果&#xff0c;以及真正最小化网络风险&#xff0c;需要全员就位&#xff0c;让安全成为每个人的责任。 早在几年前&#xff0c;企业就开始创建SOC来集中化威胁与漏洞的监视和响应。第一代SOC的目标&#xff0c;是集中管…

黑马JVM总结(五)

&#xff08;1&#xff09;方法区 它是所有java虚拟机 线程共享的区&#xff0c;存储着跟类的结构相关的信息&#xff0c;类的成员变量&#xff0c;方法数据&#xff0c;成员方法&#xff0c;构造器方法&#xff0c;特殊方法&#xff08;类的构造器&#xff09; 方法区在虚拟机…