题目链接：https://ac.nowcoder.com/acm/contest/984/B/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给定如图所示的若干个长条。你可以在某一行的任意两个数之间作一条竖线，从而把这个长条切开，并可能切开其他长条。问至少要切几刀才能把每一根长条都切开。样例如图需要切两刀。

注意：输入文件每行的第一个数表示开始的位置，而第二个数表示长度。

输入描述

Line 1: A single integer, N(2 <= N <= 32000)
Lines 2..N+1: Each line contains two space-separated positive integers that describe a leash. The first is the location of the leash's stake; the second is the length of the leash.(1 <= length <= 1e7)

输出描述

Line 1: A single integer that is the minimum number of cuts so that each leash is cut at least once.

输入

7
2 4
4 7
3 3
5 3
9 4
1 5
7 3

输出

2

解题思路

题意:给你一些长条，问至少要切几刀才能把每一根长条都切开。
思路:贪心，按结束位置从小到大排序，然后直接暴力。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 32005;
struct edge {
    int l, r;
    bool operator < (const edge & s) const {
        if (s.l != l)
            return s.r > r;
        return s.l < l;
    }
}p[N];
int vis[N];
int main() {
    int n, l, ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i].l, &l);
        p[i].r = p[i].l + l;
    }
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ans++;
            vis[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (p[j].l < p[i].r)
                    vis[j] = 1;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}