AcWing 算法基础课 贪心

一、区间问题

  1、区间选点、最大不相交区间数量

  先按右端点排序,遇到完全不相交的区间则更新当前点,并将区间数量+1.

  2、区间分组

  将区间分组使组内区间不相交,求分组的最小数量。

  左端点从小到大排序,从前往后处理每个区间,判断是否能放入当前的某个组中,

  如果能,则更新组的右端点,否则开新组。

  3、区间覆盖

  选择多个给定区间,将某一个区间覆盖,求最小选择区间数

  左端点从小到大排序

  从前往后枚举,每次选择覆盖end,且右端点最大的区间,并用右端点更新当前end

二、哈夫曼树

  AcWing 148.合并果子

  每次挑出最小的两堆进行合并

上一篇:Java学习笔记31——数组练习


下一篇:BZOJ - 3676 回文串 (回文树)