Use the constructor overload which takes a Comparator<? super E> comparator and pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you're not sure. (It's pretty straightforward though.)

As has been said elsewhere: offer and add are just different interface method implementations. In the JDK source I've got, add calls offer. Although add and offer have potentially different behaviour in general due to the ability for offer to indicate that the value can't be added due to size limitations, this difference is irrelevant in PriorityQueue which is unbounded.

Here's an example of a priority queue sorting by string length:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Here is the output:

short

medium

very long indeed

Let's look at how you're defining Comparator, because at the moment I don't think what you've written would even compile.

Comparator is an interface, meaning that you need to define a class that implements it. That is, you need to define a class that has concrete implementations of the methods described by the interface. Here, there's only one method you need to worry about - compare. (The interface also defines equals, but that's an odd choice since it's equal to the one on Object and so every class will implement this by default...)

The compare method takes two objects of the target type, and decides which one of them comes "before" the other. It returns:

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

So - you want to compare objects of whatever the class of your p1, p2 instances are (I'll call it MyClass). That means that you have to define a class:

class MyComparator implements Comparator<MyClass> {

    public int compare(MyClass a, MyClass b) {
        // TODO
    }
}

We know that the compare method should return a value depending on which of the MyClass arguments comes before the other one. You've said in your question that the one that comes first, is the one that has the smallest (i.e. earliest?) arrival time.

This is actually very easy, because that's the so-called natural ordering on java.util.Date objects - so you can just compare their arrival times against each other directly, as the result of that comparison is the same as the overall comparison.

Therefore the implementation of compare can simply be (assuming a sensibly-named accessor method):

public int compare(MyClass a, MyClass b) {
    return a.getStartTime().compareTo(b.getStartTime());
}

And there you go! You've just defined your own comparator, that will sort MyClass objects by start time ascending. You can use it in the priority queues similarly to what you have already:

Comparator<MyClass> comparator = new MyComparator();
PriorityQueue<MyClass> arrival = new PriorityQueue<MyClass>(10, comparator);

The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.

In order to implement a max-heap, you can create your own Comparator:

import java.util.Comparator;

public class MyComparator implements Comparator<Integer>
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
}

So, you can create a min-heap and max-heap in the following way:

PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());