Stall Reservations POJ - 3190(区间贪心)

男娘i 2022-03-07 00:12 261阅读 0赞

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.  
  
Help FJ by determining:

*  The minimum number of stalls required in the barn so that each cow can have her private milking period
 *  An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N  
  
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have.  
  
Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5
    1 10
    2 4
    3 6
    5 8
    4 7

Sample Output

4
    1
    2
    3
    2
    4

Hint

Explanation of the sample:  
  
Here's a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10
    
    Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
    
    Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
    
    Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
    
    Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

解题思路:

首先把所有奶牛按照开始时间早晚从早到晚进行排序,之后维护一个优先队列

优先队列的排序顺序为结束时间从早到晚,首先把第一头奶牛插入

之后开始循环,从1到N,如果插入的奶牛开始时间大于队首奶牛的结束时间,则表示两头奶牛可以在一个房间内,将这头奶牛的房间序号设置为队首奶牛的房间序号,队首奶牛出队

如果插入的奶牛开始时间小于队首奶牛的结束时间,则使房间+1

依照此贪心策略,可以得出结果

注意,优先队列的排序顺序的写法

struct SCow {
    	int id;
    	int banrsId;
    	int start_Time;
    	int end_Time;
    	friend bool operator <(SCow a, SCow b) {
    		if (a.end_Time != b.end_Time)
    			return a.end_Time > b.end_Time;   //结束时间早的在前,但这里写成大写号
    		else
    			return a.start_Time > b.start_Time;
    	}
    }SCows[MAXN];

整体代码如下:

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <stdio.h>
    using namespace std;
    const int MAXN = 50010;
    int N;
    struct SCow {
    	int id;
    	int banrsId;
    	int start_Time;
    	int end_Time;
    	friend bool operator <(SCow a, SCow b) {
    		if (a.end_Time != b.end_Time)
    			return a.end_Time > b.end_Time;   //结束时间早的在前,但这里写成大写号
    		else
    			return a.start_Time > b.start_Time;
    	}
    }SCows[MAXN];
    bool ncmp(SCow a, SCow b) {
    	return a.start_Time < b.start_Time;
    }
    bool idCmp(SCow a, SCow b) {
    	return a.id < b.id;
    }
    int main() {
    	int barns = 1;
    	priority_queue<SCow> theCowMap;  //优先队列要排序
    	scanf("%d", &N);
    	for (int i = 0; i < N; ++i) {
    		scanf("%d %d", &SCows[i].start_Time, &SCows[i].end_Time);  //起始时间和结束时间
    		SCows[i].id = i + 1;  //给牛编号
    	}
    	sort(SCows, SCows + N, ncmp);
    	//首先放入第一个元素
    	SCows[0].banrsId = barns;
    	theCowMap.push(SCows[0]);
    	for (int i = 1; i < N; ++i) {
    		if (SCows[i].start_Time <= theCowMap.top().end_Time) {
    			SCows[i].banrsId = ++barns;
    		}
    		else {
    			SCows[i].banrsId = theCowMap.top().banrsId;
    			theCowMap.pop();
    		}
    		theCowMap.push(SCows[i]);
    	}
    	printf("%d\n", barns);
    	sort(SCows, SCows + N, idCmp);
    	for (int i = 0; i < N; ++i) {
    		printf("%d\n",SCows[i].banrsId);
    	}
    	system("PAUSE");
    	return 0;
    }