组员:我、李青宸、徐铭泽、陈仲安、李秉恒
贪心
时间复杂度O(n)或排序O(nlogn)
核心思想:交换原则,交换相邻两项看看是否更优,并通过比较得出式子,得出结论
例1:小C与音乐会
有n场音乐会,每场有一个开始时间b[i]和结束时间e[i],若e[i]=b[j],第i场音乐会和第j场都能参加,问小C最多能参加几场?
按结束时间排序再贪心即可。
例2:加工生产调度
对于n个产品,分为两类,a[i]>b[i]分为1类,按a[i]升序排序;a[i]≤b[i]分为另1类,按b[i]降序排序即可