日程安排问题
<算法基础>上的贪婪算法讲的真是好啊,分析的很精到,例子也很实际,遇到了一个新问题:
日程安排,n个日程,以及数组d,d[i]表示任务i的完成期限,数组g,g[i]表示i在d[i]前完成可以获得的收益,求最大收益序列。
?
n^2的方法不说了,先快排g,降序,按照g顺序把遍历到的每个i插入数组j中,用并查集记录i的位置变化,最终时间复杂度O(nlogn)+O(n)<并查集的平摊复杂度>
?
具体实现后面贴上,此处先mark之
八卦一下,Gilles的<算法基础>我觉得甚至比算法导论还要好,贪心以及概率算法讲的尤其好