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]);
        }
    }
}