公交车司机：UVA 11389

我设法用贪婪的方法来解决这个问题。我按降序排列早晨路线，晚上路线按升序排列，然后我在晚上路线中将早晨路线的最大值设定为最小值。该解决方案已被接受。我试图证明问题具有贪婪的选择属性，也就是说，贪婪的选择是最佳解决方案的一部分。有人可以帮助证明。我只是在做这方面的证据的做法

http://cstheory.stackexchange.com/可能是一个更好的地方要问这个。 – 2012-01-27 17:34:09

@TomAnderson：cstheory是研究级别的问题。我怀疑这是一个。 – blubb 2012-01-27 17:44:15

此外，我注意到在问题中，工作限制和加班费率是用小时来描述的，但是长度是用米来描述的。噢，每天的限制是20个小时 - 我想孟加拉国的公交车司机是非常努力的！ – 2012-01-27 17:54:55

回答