题目描述

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

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

输入描述:

Line 1: A single integer,
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.

输出描述:

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

示例1

输入
7
2 4
4 7
3 3
5 3
9 4
1 5
7 3
输出
2

解答

题目大意： 输入一个区间，输出最少需要几刀才可以将每个区间都切开
思路 : 先排序，将尾部靠前的放前边，其次将首部靠前的放前边，从第一个开始遍历，如果遇到该点的尾小于下一个点的头，那么 刀数 + 1， 注意输入的是首部位置和长度 （以为是首尾位置WA了好几发）
AC代码 ： 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
 
struct node
{
    int x, y;
}p[MAXN];
bool cmp (node a, node b) {
    if (a.y == b.y) return a.x < b.x;
    else return a.y < b.y;
}
int n, ans, ui, vi;
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ui >> vi;
        p[i].x = ui;
        p[i].y = ui + vi - 1;   // 记录尾部
    }
    sort (p, p + n, cmp);
    for (int i = 0; i < n - 1; i++) {
        bool flag = 1;
        for (int j = i + 1; j < n; j++) {
            if (p[i].y < p[j].x) {flag = 0, ans++, i = j - 1; break;}  //更新下一个
        }
        if (flag) break;
    }
    cout << ans + 1 << endl;
    return 0;
}

来源：东野圭吾#