数据结构与算法–关键路径

文章预览

作者：sunhaiyu 关键路径与无环加权有向图的最长路径 现在考虑一个这样的问题：你今天事情比较多，要洗衣服、做作业还要烧水洗澡，之后出去找朋友玩。假设洗衣服要20分钟，烧水要30分钟，做作业的话你把朋友做好的带回来抄，只需要10分钟。你想能早些去找朋友，但在那之前又必须将那些事做完，你要怎么安排呢？很容易想到，这三者同时进行：打好水开始烧水，衣服扔进洗衣机，回书桌抄作业…20分钟后作业写完了，衣服也洗好了，水还有10分钟水才烧开，利用这时间把洗好的衣服晾晒好，差不多水也烧开了，好了最后去洗澡。简直一气呵成，这是我们能花费的最少时间了，在这个例子中刚好等于所有任务中持续时间最长的那个。（你做完了作业才想起来 ………………………………