贪心问题 : 区间分组
题目描述
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B,每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
输入格式
第1行:输入一个整数N。
第2..N+1行:第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B,数之间用空格隔开。
输出格式
第1行:输入一个整数,代表所需最小畜栏数。
第2..N+1行:第i+1行输入第i头牛被安排到的畜栏编号,编号是从1开始的 连续 整数,只要方案合法即可。
数据范围
1≤N≤50000,
1≤A,B≤1000000
样例
输入样例:
5
1 10
2 4
3 6
5 8
4 7
输出样例:
4
1
2
3
2
4
求区间数量的AC代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define N 50001
int n,ans[N],now;
struct line
{
int l,r;
bool operator < (const line &x)const
{
return l < x.l;
}
}a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].l >> a[i].r;
priority_queue < int , vector < int > , greater < int > > head;
for (int i = 1; i <= n; i++)
{
if (head.empty() || head.top() >= now.l) head.push(a[i].r),ans[i] = ++now;
else
{
head.pop();
head.push(a[i].r);
}
}
cout << head.size();
return 0;
}
因为这里要求方案,所以要麻烦些,献上AC代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define N 50001
#define l first
#define r second
typedef pair < int , int > PII;
int n,ans[N];
pair < PII , int > a[N]; // PII记录左右端点,int下标
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].first.l >> a[i].first.r;
a[i].second = i;
}
sort(a + 1,a + n + 1);
priority_queue < PII , vector < PII > , greater < PII > > head;
for (int i = 1; i <= n; i++)
{
if (head.empty() || head.top().first >= a[i].first.l) // 如果没有区间存在或Max_r比当前区间的左端点大,就开一个
{
PII stall = {a[i].first.r , head.size() + 1};
ans[a[i].second] = stall.second; // 更新答案数组
head.push(stall);
}
else
{
PII stall = head.top();
head.pop();
stall.first = a[i].first.r; // 更改一下这个区间的Max_r
ans[a[i].second] = stall.second;
head.push(stall);
}
}
cout << head.size() <<endl;
for (int i = 1; i <= n; i++)
cout << ans[i] << endl;
return 0;
}