美团外卖日订单数已经超过1200万，实时调度系统是背后的重要技术支撑，其中涉及很多复杂的算法，下面的题目是某类场景的抽象，1上，求他最多能完成多少个配送任务，在整个过程中，我们忽略了取餐与最后给用户递餐的时间，只考虑花费在路程上的时间，另外，允许在一个点逗留。
美团外卖日订单数已经超过1200万，实时调度系统是背后的重要技术支撑，其中涉及很多复杂的算法。下面的题目是某类场景的抽象。 一张 n n 个点 m m 条有向边的图上，有 q q 个配送需求，需求的描述形式为( s_i , t_i , l_i , r_i s i ,t i ,l i ,r i )，即需要从点 s_i s i 送到 t_i t i ， 在时刻 l_i l i 之后（包括 l_i l i ）可以在 s_i s i 领取货物，需要在时刻 r_i r i 之前（包括 r_i r i ）送达 t_i t i ，每个任务只需完成一次。 图上的每一条边均有边权，权值代表外卖配送员通过这条边消耗的时间。在时刻 0 有一个配送员在 点 1 1 上，求他最多能完成多少个配送任务。 在整个过程中，我们忽略了取餐与最后给用户递餐的时间（实际场景中这两个时间是无法省略的），只考虑花费在路程上的时间。另外，允许在一个点逗留。
（图片来源网络，侵删）
标签： HBC13252送外卖2题解
