算法入门课第一节–练习–Selfish Grazing 题解

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Each of Farmer John’s N (1 <= N <= 50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number line. Cow i’s favorite grazing range starts at location Si and ends at location Ei (1 <= Si < Ei; Si < Ei <= 100,000,000).
Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows i and j can only graze at the same time if either Si >= Ej or Ei <= Sj. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.

Consider a set of 5 cows with ranges shown below:
  ... 1    2    3    4    5    6    7    8    9   10   11   12   13 ...
  ... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1:      <===:===>          :              :              :
Cow 2: <========:==============:==============:=============>:
Cow 3:          :     <====>   :              :              :
Cow 4:          :              :     <========:===>          :
Cow 5:          :              :     <==>     :              :

These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively.
For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together,so it is impossible for four or more cows to graze.

输入格式：

• Line 1: A single integer: N
• Lines 2..N+1: Line i+1 contains the two space-separated integers: Si and Ei

输出格式：

• Line 1: A single integer representing the maximum number of cows that can graze at once.

样例：

输入：

5 
2 4 
1 12 
4 5 
7 10 
7 8 

输出：

3

Solution

思路：

贪心算法，建立结构体进行排序，以右端点越靠前为最优贪心解。

代码：

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    ll a,b;
}a[50005];

bool cmp(node tx,node ty){
    if(tx.b<ty.b) return true;
    if(tx.b>ty.b) return false;
    if(tx.a<ty.a) return true;
    return false;
}

int main(){
    ll n;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>a[i].a>>a[i].b;
    }

    sort(a,a+n,cmp);
    ll cnt = 0,r=0;
    for(int i  = 0 ;i<n;i++){
        if(a[i].a >= r){
            cnt++;
            r = a[i].b;
        }
    }
    cout<<cnt;


    return 0;
}