Selfish Grazing(贪心 区间覆盖)
Selfish Grazing
https://ac.nowcoder.com/acm/problem/24867
题目描述
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.
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.
示例1
输入
5 2 4 1 12 4 5 7 10 7 8
输出
3
题意
给定若干个区间，找出最多有几个互相不重叠的区间
思路
对区间右端点进行从小到大排序，可以这样理解，结束得越早，我更有机会开始下一个新区间
代码
//Selfish Grazing(贪心 区间覆盖)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50010;
struct S
{
int l;
int r;
};
int n;
S s[N];
bool cmp(S a , S b)
{
return a.r < b.r;
}
int main()
{
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
scanf("%d %d" , &s[i].l , &s[i].r);
sort(s , s + n , cmp);
int cnt = 1 , now = s[0].r;
for(int i = 1 ; i < n ; i++)
{
if(s[i].l >= now)
{
cnt++;
now = s[i].r;
}
}
printf("%d\n" , cnt);
return 0;
} 牛客算法竞赛入门课第一节习题题解 文章被收录于专栏
入门课第一节习题题解
Momenta公司福利 554人发布
