题解 | County Fair-牛客假日团队赛2G题
G-County Fair Events_牛客假日团队赛2
https://ac.nowcoder.com/acm/contest/924/G
题目描述
Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the)
special events as he possibly can.
He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!).
He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!).
Given a list of the events that FJ might wish to attend, with their start times)
and their durations )
, determine the maximum number of events that FJ can attend. FJ never leaves an event early.
输入描述:
Line 1: A single integer, N.
Lines 2..N+1: Each line contains two space-separated integers, T and L, that describe an event that FJ might attend.
输出描述:
Line 1: A single integer that is the maximum number of events FJ can attend.
示例1
输入
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
输出
4
说明
Graphic picture of the schedule:
FJ can do no better than to attend events 1, 2, 3, and 4.
解答
有n个任务，每个任务有开始时间和持续时间，让你求最多完成几个任务。
最大不相交覆盖问题，对线段的右端点进行升序排序，每加入一个线段，然后选择后面若干个右端点相同的线段，选择左端点最大的那一条，如果加入以后不会跟之前的线段产生公共部分，那么就加入，否则就继续判断后面的线段。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+ 7;
struct node
{
int x, y;
}a[N];
bool cmp(node a, node b)
{
if(a.y == b.y) a.x > b.x;
return a.y < b.y;
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d%d",&a[i].x, &a[i].y);
a[i].y += a[i].x;
}
sort(a, a + n, cmp);
int cnt = 1, p = 0;
for(int i = 1; i < n; i++)
{
if(a[i].x >= a[p].y)
cnt++, p = i;
}
cout << cnt << endl;
} 来源：sugarbliss
百威成长空间 50人发布
投递58到家等公司10个岗位 >