力扣每日一题--2050. 并行课程 III(拓补排序例题)

题目传送门
题目描述:
给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 r e l a t i o n s [ j ] = [ p r e v C o u r s e j , n e x t C o u r s e j ] relations[j] = [prevCoursej, nextCoursej] relations[j]=[prevCoursej,nextCoursej],表示课程 p r e v C o u r s e j prevCoursej prevCoursej 必须在课程 n e x t C o u r s e j nextCoursej nextCoursej 之前 完成(先修课的关系)。同时给你一个下标从 0 开始的整数数组 t i m e time time ,其中 t i m e [ i ] time[i] time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数:

如果一门课的所有先修课都已经完成,你可以在 任意 时间开始这门课程。
你可以 同时任意门课程
请你返回完成所有课程所需要的 最少 月份数。

注意:测试数据保证一定可以完成所有课程(也就是先修课的关系构成一个有向无环图)。

示例 1:
在这里插入图片描述

输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此,answer[0] = 8,以此类推。

示例 2:
在这里插入图片描述

输入:n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
输出:12
解释:上图展示了输入数据所表示的先修关系图,以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 ,2 和 3 。
在月份 1,2 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始,也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。
课程 5 需在课程 1,2,3 和 4 之后开始,也就是在 max(1,2,3,7) = 7 月开始。
所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。

解题思路

这个题其实类似于我们算数据结构中AOE图的起点到终点的最少权值。
在建完图之后, 按拓扑排序的顺序更新达每节课的最早完成时间
我们让 r e a c h [ i ] reach[i] reach[i] 表示完成第 i i i 门课程的最短时间,然后若结点u和v之间有边,则v的最早完成时间就是v的所有现行课程同时进行的最早完成时间加上v的课程时间,于是则有: r e a c h [ v ] = m a x ( r e a c h [ u ] + t i m e [ v − 1 ] , r e a c h [ v ] ) ; reach[v] = max(reach[u] + time[v - 1], reach[v]); reach[v]=max(reach[u]+time[v1],reach[v]);
拓补排序结束之后,reach中的最大值即为所求的答案。

AC代码如下

class Solution {
public:
    static const int maxn = 5e4+5;
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<int>G[n+2];
        queue<int>q;
        vector<int>reach(n + 2, 0);
        int indegree[maxn] = {0}, ans = 0;
        for(auto relation : relations) { // 建图
            G[relation[0]].push_back(relation[1]);
            indegree[relation[1]] ++; // 入度加一
        }
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                reach[i] = time[i-1];
                q.push(i);
            }
        }
        while(!q.empty()) { // 拓补排序
            int u = q.front();
            q.pop();
            for(int i = 0; i < G[u].size(); i++) {
                int v = G[u][i];
                reach[v] = max(reach[u] + time[v - 1], reach[v]);
                indegree[v]--;
                if(indegree[v] == 0) q.push(v);
            }
        }
        for(auto i : reach) ans = max(ans, i);
        return ans;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第五章 HL7 架构和可用工具 - 创建新的自定义架构

文章目录 第五章 HL7 架构和可用工具 - 创建新的自定义架构创建新的自定义架构定义新段 第五章 HL7 架构和可用工具 - 创建新的自定义架构 创建新的自定义架构 要从管理门户启动自定义架构编辑器&#xff0c;请从主页选择互操作性 > 互操作 > HL7 v2.x >HL7 v2.x 架…

Python-如何使用正则表达式

如何利用Python使用正则表达式 目录 正则表达式常用匹配规则 ​编辑re库的使用 match()方法&#xff1a; search()方法: findall()方法 : sub()方法: compile()方法; 通用匹配 贪婪与非贪婪匹配 贪婪匹配 非贪婪匹配 修饰符 转义匹配 正则表达式是处理字符的强大…

RabbitMQ 教程 | 第5章 RabbitMQ 管理

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

MATLAB | 如何绘制这样的描边散点图?

part.-1 前前言 最近略忙可能更新的内容会比较简单&#xff0c;见谅哇&#xff0c;今日更新内容&#xff1a; part.0 前言 看到gzhBYtools科研笔记(推荐大家可以去瞅瞅&#xff0c;有很多有意思的图形的R语言复现&#xff01;&#xff01;)做了这样一张图&#xff1a; 感觉很…

【论文阅读24】Better Few-Shot Text Classification with Pre-trained Language Model

论文相关 论文标题&#xff1a;论文标题&#xff1a;Label prompt for multi-label text classification&#xff08;基于预训练模型对少样本进行文本分类&#xff09; 发表时间&#xff1a;2021 领域&#xff1a;多标签文本分类 发表期刊&#xff1a;ICANN&#xff08;顶级会…

CASAIM自动化平面度检测设备3D扫描零部件形位公差尺寸测量

平面度是表面形状的度量&#xff0c;指示沿该表面的所有点是否在同一平面中&#xff0c;当两个表面需要连接在一起形成紧密连接时&#xff0c;平面度检测至关重要。 CASAIM自动化平面度检测设备通过搭载领先的激光三维测头和智能检测软件自动获取零部件高质量测量数据&#xf…

【LeetCode】最小路径和

最小路径和 题目描述算法流程编程代码 链接: 最小路径和 题目描述 算法流程 编程代码 class Solution { public:int minPathSum(vector<vector<int>>& grid) {int m grid.size();int n grid[0].size();vector<vector<int>> dp(m1,vector<in…

Ae 效果:CC Kernel

颜色校正/CC Kernel Color Correction/CC Kernel CC Kernel&#xff08;CC 卷积核&#xff09;效果主要用于图像的卷积处理&#xff0c;通过在卷积矩阵中设置不同的权重值&#xff0c;可以实现图像的锐化 Sharpen、模糊 Blur、查找边缘 Find Edges以及浮雕 Emboss等效果。 ◆ …

<C语言> 预处理和宏

1.预定义符号 __FILE__ //进行编译的源文件 __LINE__ //文件当前的行号 __DATE__ //文件被编译的日期 __TIME__ //文件被编译的时间 __STDC__ //如果编译器遵循ANSI C&#xff0c;其值为1&#xff0c;否则未定义这些预定义符号都是C语言内置的。 举个例子&…

谷歌: 安卓补丁漏洞让 N-days 与 0-days 同样危险

近日&#xff0c;谷歌发布了年度零日漏洞报告&#xff0c;展示了 2022 年的野外漏洞统计数据&#xff0c;并强调了 Android 平台中长期存在的问题&#xff0c;该问题在很长一段时间内提高了已披露漏洞的价值和使用。 更具体地说&#xff0c;谷歌的报告强调了安卓系统中的 &quo…

vue3常用API之学习笔记

目录 一、setup函数 vue2与vue3变量区别 二、生命周期 三、reactive方法 四、ref方法 1、简介 2、使用 3、ref与reactive 4、获取标签元素或组件 五、toRef 1、简介 2、ref与toRef的区别 六、toRefs 七、shallowReactive 浅reactive 1、简介 2、shallowreactiv…

Debian 12.1 “书虫 “发布,包含 89 个错误修复和 26 个安全更新

导读Debian 项目今天宣布&#xff0c;作为最新 Debian GNU/Linux 12 “书虫 “操作系统系列的首个 ISO 更新&#xff0c;Debian 12.1 正式发布并全面上市。 Debian 12.1 是在 Debian GNU/Linux 12 “书虫 “发布六周后推出的&#xff0c;目的是为那些希望在新硬件上部署操作系统…

JMeter发送get请求并分析返回结果

在实际工作的过程中&#xff0c;我们通常需要模拟接口&#xff0c;来进行接口测试&#xff0c;我们可以通过JMeter、postman等多种工具来进行接口测试&#xff0c;但是工具的如何使用对于我们来说并不是最重要的部分&#xff0c;最重要的是设计接口测试用例的思路与分析结果的能…

硬核来袭!中国AI大模型峰会“封神之作”,开发者们不容错过!

大家好&#xff0c;我是herosunly。985院校硕士毕业&#xff0c;现担任算法研究员一职&#xff0c;热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名&#xff0c;CCF比赛第二名&#xff0c;科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的…

PDF文件忘记密码,怎么办?

PDF文件设置密码分为打开密码和限制密码&#xff0c;忘记了密码分别如何解密PDF密码&#xff1f; 如果是限制编辑密码忘记了&#xff0c;我们可以试着将PDF文件转换成其他格式来避开限制编辑&#xff0c;然后重新将文件转换回PDF格式就可以了。 如果因为转换之后导致文件格式…

MapBox 做聚合图点位聚合效果实现教程

最近收到一个需求&#xff0c;要对 5000的点位进行展示。直接展示的话满屏幕都是点&#xff0c;效果太丑&#xff0c;于是想到了聚合&#xff0c;聚合有很多种方案。首先你可以手动的些代码来计算某个范围内的点的数量然后再把聚合的结果展示在这个范围的某个位置。这针对于简单…

PMP证书查询 ACP证书查询 PMP/ACP证书查询 PMP证书真伪查询 ACP证书真伪查询PMI证书查询

PMP证书查询 ACP证书查询 PMP/ACP证书查询 PMP证书真伪查询 ACP证书真伪查询PMI证书查询 一、查询步骤 1、地址&#xff1a; https://www.pmi.org/certifications/certification-resources/registry 2、查询截图&#xff1a; 2.1、证书类型如下&#xff1a; 3、查到证书 4、没…

python语言程序设计基础(第2版)课后答案

这篇文章主要介绍了python语言程序设计基础第二版课后答案&#xff0c;具有一定借鉴价值&#xff0c;需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获&#xff0c;下面让小编带着大家一起了解一下。 第一章 初识Python 1.1学好Python的关键 刷代码&#xff1a;寻找一个…

安科瑞电动机保护器产品在污水处理厂的应用-安科瑞黄安南

应用场景 功能 1&#xff09;排污泵经常会出现过载、缺相等问题&#xff0c;导致电机烧坏&#xff1b; 2&#xff09;为电动机提供完善的保护&#xff0c;并具备多种事件记录追忆功能&#xff1b; 3&#xff09;全电参量测量&#xff0c;包括但不限于三相电流、三相电压、有…

简约好看的帮助中心创建案例,赶紧点赞收藏!

在线帮助中心创建案例是提供用户支持和解决问题的有效方式之一。一个简约好看的帮助中心案例能够帮助用户快速找到需要的信息并解决问题&#xff0c;同时也能提升用户体验&#xff0c;增加点赞和收藏的可能性。 帮助中心创建案例分享&#xff1a; 酷学院&#xff1a; 酷渲&a…