Greedy

Don’t be greedy !

贪心

贪心，就是 局部最优解 和 全局最优解 保持一致。故只需要考虑当前收益，而不用考虑后续情况。

贪心需要，一个固定的方向。

最小覆盖 / 最大独立集

最小覆盖：

给定 个区间，以 形式给出。问最少放多少个点，能覆盖所有区间。

对于答案点集里的点：若按从小到大排好序，最小的点一定要覆盖右端点最小的区间，不然这个区间就不能被覆盖了。且对于右端点最小的区间，将点放在右端点处是最不浪费的（即可能覆盖的区间数最多。由此可得，贪心的思路为：将所有区间按右端点的大小排好序，然后选择在右端点最小的区间的右端点上放一个点，记录当前最大的点的位置，若某个区间的左端点比这个点的位置要大，则该区间需要重新选一个点进行覆盖。

最大独立集：

极大化区间数量，要求：区间之间无交。

pair<int, int> a[N]; // pair 默认第一维为第一关键字，第二维为第二关键字，所以第一维存 r，第二维存 l，方便后面的排序。

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int l = rd(), r = rd();
        a[i].first = r; a[i].second = l;
    }
    sort(a + 1, a + 1 + n);
    int mxpos = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (mxpos < a[i].second) {
            ++ans;
            mxpos = a[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}

https://www.luogu.com.cn/problem/P1803

#include<bits/stdc++.h>
using namespace std;
#define N 1000007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

pair<int, int> a[N]; // pair 默认第一维为第一关键字，第二维为第二关键字，所以第一维存 r，第二维存 l，方便后面的排序。

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int l = rd(), r = rd();
        a[i].first = r - 1; a[i].second = l;
    }
    sort(a + 1, a + 1 + n);
    int mxpos = -1, ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (mxpos < a[i].second) {
            ++ans;
            mxpos = a[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}

http://www.51nod.com/Challenge/Problem.html#problemId=3086

#include<bits/stdc++.h>
using namespace std;
#define N 2000007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

pair<int, int> a[N]; // pair 默认第一维为第一关键字，第二维为第二关键字，所以第一维存 r，第二维存 l，方便后面的排序。

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int l = rd(), r = rd();
        if (l > r) swap(l, r);
        a[i].first = r - 1; a[i].second = l;
    }
    sort(a + 1, a + 1 + n);
    int mxpos = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (mxpos < a[i].second) {
            ++ans;
            mxpos = a[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}

最小覆盖2

最小化区间数量，使得：区间的并能覆盖整个区间。

首先 l = 1 的所有区间里，必须选一个，选哪个呢？要选 r 最大的。然后要尽可能不选，用 mxpos 记录当前可以不选的区间里 r 的最大值，r 记录当前已选区间 r 的最大值。

int mxpos = 0, r = 0, ans = 0;

for (int i = 1; i <= n; ++i) {
    if (a[i].second > r + 1) {
        r = mxpos;
        ++ans;
    }
    mxpos = max(mxpos, a[i].first);
}

http://poj.org/problem?id=2376

#include<bits/stdc++.h>
using namespace std;
#define N 2000007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

pair<int, int> a[N]; // pair 默认第一维为第一关键字，第二维为第二关键字，所以第一维存 r，第二维存 l，方便后面的排序。

int main() {
    int n = rd(), t = rd();
    for (int i = 1; i <= n; ++i) {
        int l = rd(), r = rd();
        if (l > r) swap(l, r);
        a[i].first = l; a[i].second = r;
    }
    sort(a + 1, a + 1 + n);
    int mxpos = 0, r = 0, ans = 0;

    for (int i = 1; i <= n; ++i) {
        if (a[i].first > r + 1) {puts("-1"); return 0;}
        r = max(r, a[i].second);
    }
    if (r != t) {puts("-1"); return 0;}

    r = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i].first > r + 1) {
            r = mxpos;
            ++ans;
        }
        mxpos = max(mxpos, a[i].second);
    }
    ans += (r != t);
    cout << ans << endl;
    return 0;
}