题目均来自acwing.com

AcWing 905. 区间选点

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。

思路：每个区间迟早要选出一个符合要求的点，而对于一个大区间包含小区间的情况，小区间满足大区间一定满足，反之不亦然，所以不妨先考虑小区间。
按右端点从小到大排序。首先考虑第一个区间，反正一定要选一个点，不妨选右端点，显然，这样能尽可能覆盖较多（左端点在第一段右端点的左边的）区间，把这个点设为pos。依次枚举每一个区间，如果它的左端点小于等于pos，则一定已经被覆盖了；如果他的左端点大于等于pos，则需要选一个新点，同理可知应该选右端点，重复上述过程即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Seg {
  int l, r;
}seg[N];

bool cmp(Seg a, Seg b) {
  if (a.r != b.r) return a.r < b.r;
  else return a.l > b.l;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 908. 最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。

思路：首先考虑第一个区间选哪个。按右端点从小到大排序，选择右端点最小的区间，可以尽可能地提高选择的余地。在数轴剩下的部分同样这样做即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;

struct Seg {
  int l, r;
} seg[N];

bool cmp(Seg a, Seg b) {
  return a.r < b.r;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 906. 区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

思路：
图书馆中最少需要安排多少个座位，使得N个在不同时段[ai,bi]学习的人恰好都有座？
只要座位数大于同时学习的最大人数即可。。。（反正每个来到的人都会自动坐在空位上。。。）
我也不知道这叫啥思路，“人工智能”？
用差分+前缀和的话，数组有点大，自然想到离散化。
其实没必要，将“坐下”和“离开”的所有操作按时间先后排序，按照时间轴依次进行（座位+1/-1）即可。
同一个时间点既有来学习的也有离开的，需要为来学习的人加一个座位。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Seg {
  int l, r;
}seg[N];

bool cmp(Seg a, Seg b) {
  if (a.r != b.r) return a.r < b.r;
  else return a.l > b.l;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 907. 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 ?1。

思路：
首先考虑覆盖了s点的区间，显然要选右端点最靠右的。
将所选区间的右端点当作新的s继续操作即可。
扫一遍即可，具体实现见代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, s, t;
struct Seg {
  int l, r;
} seg[N];

bool cmp(Seg a, Seg b) {
  return a.l < b.l;
}
int main() {
  cin >> s >> t >> n;
  for (int i = 0; i < n; i++) {
    cin >> seg[i].l >> seg[i].r;
  }
  sort(seg, seg + n, cmp);
  int pos = s, maxr = -inf, ans = 0;
  for (int i = 0; i < n; i++) {
    if (seg[i].l > pos) pos = maxr, ans++;
    if (seg[i].l <= pos && seg[i].r >= pos && seg[i].r > maxr) {
      maxr = seg[i].r;
    }
    if (pos >= t) break;
  }
  if (pos < t && maxr >= t) pos = maxr, ans++;
  if (pos >= t) cout << ans;
  else cout << -1;
  return 0;
}

贪心算法入门——区间问题