Java Priority Queue is not working

Debugging Help
#1

Problem Info

USACO 2018 December Contest, Silver Problem 2. Convention II

http://www.usaco.org/index.php?page=viewproblem2&cpid=859

My Work

import java.io.*;
import java.util.*;

public class Convention2 {
    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio("convention2");

        int nCows = io.nextInt();

        PriorityQueue<Cow> arrivalOrder = new PriorityQueue<>(new Comparator<Cow>() {
			@Override
			public int compare(Cow o1, Cow o2) {
				return Integer.compare(o1.arrivalTime, o2.arrivalTime);
			}
		});

        for(int c = 0; c < nCows; c++)
		{
			arrivalOrder.add(new Cow(io.nextInt(), io.nextInt(), c + 1));
		}

        PriorityQueue<Cow> waitingQueue = new PriorityQueue<>(new Comparator<Cow>() {
			@Override
			public int compare(Cow o1, Cow o2) {
				return Integer.compare(o1.seniority, o2.seniority);
			}
		});

		System.out.println(arrivalOrder);
    }

    static class Cow
	{
    	int arrivalTime;
    	int samplingTime;
    	int seniority;
    	int endingTime;

    	Cow(int arrivalTime, int samplingTime, int seniority)
		{
			this.arrivalTime = arrivalTime;
			this.samplingTime = samplingTime;
			this.seniority = seniority;
			endingTime = arrivalTime + samplingTime;

		}

		@Override
		public String toString()
		{
			return " {" + arrivalTime + " --> " + endingTime + " Seniority: " + seniority + "} ";
		}
	}

	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;

		// standard input
		public Kattio() {
			this(System.in, System.out);
		}

		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}

		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(new FileWriter(problemName + ".out"));
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}

		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) {
			}
			return null;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}

Here I wanted to make a priority queue called arrivalOrder that stored all the cows sorted by thier arrival time. However when I print out the priority queue, the order is incorrect:
[ {10 --> 27 Seniority: 4} , {20 --> 70 Seniority: 3} , {25 --> 28 Seniority: 1} , {105 --> 135 Seniority: 2} , {100 --> 110 Seniority: 5} ]

Here the cow who arrives at 105 is before the cow who arrives at 100, which is wrong.

How can I fix this?

#2

PriorityQueues in Java are not guaranteed to print completely in order (java - Print content of priority queue - Stack Overflow, java - Why does PriorityQueue.toString return the wrong element order? - Stack Overflow). I believe it’s because they are implemented in such a way that only guarantees that the first element is the lowest – the rest aren’t necessarily in order, which is what makes them more efficient than TreeSets. If you really want to get the true order, you’ll probably have to .poll() each element and print it out separately. Most likely there’s no issue, though, your code looks fine to me.
(Also, unrelated, but for simpler/more concise code note you don’t have to create new comparators for the PriorityQueue, lambdas will work just fine).

1 Like