切长条(贪心 区间覆盖)

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

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

输入描述:

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.

示例1

输入

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

输出

2

思路

//切长条(贪心 区间覆盖)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 32010;
struct S
{
	int start;
	int end;
	
	bool operator < (const S t)const
	{
		return this->end < t.end;
	}
};

S s[N];

int main()
{
 	int n;
 	scanf("%d" , &n);
 	for(int i = 0 ; i < n ; i++)
 	{
 		scanf("%d %d" , &s[i].start , &s[i].end);
 		s[i].end += s[i].start - 1;
	}
 		
 	sort(s , s + n);
 	
 	int cnt = 1;
 	int last = s[0].end;
 	for(int i = 1 ; i < n ; i++)
 	{	 
		if(last < s[i].start)
		{
			cnt++;
			last = s[i].end;
		}	
	}
	
	printf("%d\n" , cnt);
	return 0; 
}