线段覆盖 洛谷-P1803
问题简述
给定 \(N\) 个正整数区间 \((l_i,r_i)\)，问能选择的最多互不重合的区间数.
做法
按左端点为第一关键字升序，右端点为第二关键字降序排序，能选择的直接选择即可.
最少点覆盖全部区间 CSP-S2024 T2 超速检测第二问
问题简述
给定 \(N\) 个正整数区间 \([l_i,r_i]\)，选取一些点，使得每个区间都至少有一个点在区间中，求最少点数.
做法
按右端点升序排序，依次判断区间，如果当前区间已有点则跳过，没有点则加右端点作为新点，每次维护当前最远点即可.
最多挤奶问题 洛谷 P3093
问题简述
给定 \(N\) 头奶牛，有两个变量 \(g_i,d_i\)，表示：如果在时间 \(d_i\) 前（不含时间 \(d_i\)）挤奶，就能获得 \(g_i\) 的奶量，每次挤奶固定 \(1\) 单位时间，现在是第 \(0\)秒，问最多获得多少奶量.
做法
按奶量降序排序，对于一头奶牛 \(i\)，从 \(d_i-1\) 开始往前枚举，遇到一个空余时间就加入，如果没有空余时间则跳过.