Stall Reservation (POJ 3190)
This problem is for a greedy strategy. At first we sort the cows by their start milking time and from the first
we start serve them with a stall. Instead of deciding number of stall at the beginning, we allocate a new stall
when needed. Once a new cow comes, we check if there is a free stall. If true, we allocate the cow to the
free stall, or we have to allocate a new one. As to speed up the finding free stalls procedure, we can use a
PriorityQueue
which sort cows in service by their end milking time. So when a new cow comes, we first poll
cows from the queue if the serving has already finished before we try to serve new cow.
import java.io.*;
import java.util.*;
class Interval implements Comparable<Interval>{
int x;
int y;
int id;
public Interval(int x, int y, int id) {
this.x = x;
this.y = y;
this.id = id;
}
public int compareTo(Interval that) {
Interval a = this;
Interval b = that;
return ((a.x == b.x) ? b.y - a.y : a.x - b.x);
}
}
public class StallReservation {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
Interval[] intervals = new Interval[N];
for (int i = 0; i < N; i++) {
intervals[i] = new Interval(in.nextInt(), in.nextInt(), i);
}
Arrays.sort(intervals);
PriorityQueue<Interval> pq = new PriorityQueue<Interval>(N, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return (a.y == b.y) ? a.x - b.x : a.y - b.y;
}
});
int count = 0;
int[] arrange = new int[N];
for (Interval i : intervals) {
if ((!pq.isEmpty()) && pq.peek().y < i.x) {
arrange[i.id] = arrange[pq.poll().id];
} else {
arrange[i.id] = (++count);
}
pq.offer(i);
}
System.out.println(count);
for (int i = 0; i < N; i++) {
System.out.println(arrange[i]);
}
}
}