Selfish Grazing

Selfish Grazing

题目描述

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

题目大意

场有N头牛，每头牛都有它喜欢的放牧区间[si,Ei]没有牛愿意与其他人共享任何放牧区域。因此，如果Si> = Ej或Ei <= Sj，则两只母牛i和j只能同时放牧。FJ希望知道给定的一组奶牛可以同时放牧的最大奶牛数量及其偏好。

思路

贪心 维护区间，按右端点进行排序，如果坐端点大于右端点（代表不重合） 则更新新的右端点。

#include<bits/stdc++.h>
using namespace std;
struct date{
    int l=0;
    int r=0;
}cow[50005];
bool cmp(date a,date b)
{
    return a.r<b.r;
}
int main()
{
    //牧场有N头牛，每头牛都有它喜欢的放牧区间[si,Ei]
    //没有牛愿意与其他人共享任何放牧区域。
    //因此，如果Si> = Ej或Ei <= Sj，
    //则两只母牛i和j只能同时放牧。
    //FJ希望知道给定的一组奶牛可以同时放牧的最大奶牛数量及其偏好。
    int n,sum=0,right=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&cow[i].l,&cow[i].r);
    }
    sort(cow,cow+n,cmp);
    right=cow[0].r;
    for(int i=1;i<n;i++)
    {
        if(cow[i].l>=right)
        {
            sum++;
            //printf("%d %d ",cow[i].l,right);
            right=cow[i].r;
        }
    }
    printf("%d",sum+1);
    return 0;
 }