[HackerRank]Java優先佇列(Java Priority Queue)

題目描述

這個題目將會測試您對Java優先佇列的認知。

您必須要處理兩種事件：ENTER(一個學生進入佇列)和SERVED。

一個獨特的記號將會被指派給任何一個進來這個佇列的學生。這個佇列會依照以下標準來服務學生：

給定一系列的事件，輸出被服務的學生們的名字。如果佇列是空的，輸出「EMPTY」。

原題網址

輸入格式

第一行輸入是一個整數n，表示事件的數量，範圍在2到1000之間(包含2和1000)。接下來的n行，每行有以下兩種格式：

CGPA的範圍在0.0到4.0之間(包含0.0到4.0)。token的範圍在1到10⁵之間(包含1和10⁵)，每個token皆不重複。name的長度在2到30之間(包含2和30)。

輸出格式

印出所有經過一連串事件後，最後沒被服務的學生。如果所有佇列中的學生都被服務了，輸出「EMPTY」。

範例輸入

範例輸出

額外解釋

ENTER John 3.75 50：

ENTER Mark 3.8 24：

ENTER Shafaet 3.7 35：

SERVED：

SERVED：

ENTER Samiha 3.85 36：

SERVED：

ENTER Ashley 3.9 42：

ENTER Maria 3.6 46：

ENTER Anik 3.95 49：

ENTER Dan 3.95 50：

SERVED：

解題概念

使用Java的PriorityQueue物件來儲存Student物件，並替PriorityQueue物件實作Comparator介面的compare方法來對Student物件進行排序。

PriorityQueue物件的offer方法可以增加元素到PriorityQueue物件內，而poll方法可以從PriorityQueue物件內拿出優先權最高的元素。

參考答案

package hackerrank;

import java.util.*;

class Student {

    private int token;
    private String fname;
    private double cgpa;

    public Student(int id, String fname, double cgpa) {
        super();
        this.token = id;
        this.fname = fname;
        this.cgpa = cgpa;
    }

    public int getToken() {
        return token;
    }

    public String getFname() {
        return fname;
    }

    public double getCgpa() {
        return cgpa;
    }
}

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int totalEvents = Integer.parseInt(in.nextLine());
        final PriorityQueue<Student> q = new PriorityQueue<>((s1, s2) -> {
            final double cgpaDiff = s2.getCgpa() - s1.getCgpa();
            if (cgpaDiff > 0) {
                return 1;
            } else if (cgpaDiff < 0) {
                return -1;
            }
            final int nameCompare = s1.getFname().compareTo(s2.getFname());
            if (nameCompare != 0) {
                return nameCompare;
            }
            return s1.getToken() - s2.getToken();
        });
        while (totalEvents > 0) {
            String event = in.next();

            switch (event) {
                case "ENTER": {
                    final String name = in.next();
                    final double cgpa = in.nextDouble();
                    final int token = in.nextInt();
                    q.offer(new Student(token, name, cgpa));

                }
                break;
                case "SERVED": {
                    q.poll();
                }
                break;
            }
            totalEvents--;
        }
        if (q.isEmpty()) {
            System.out.println("EMPTY");
        } else {
            final StringBuilder sb = new StringBuilder();
            while (!q.isEmpty()) {
                sb.append(q.poll().getFname()).append("\n");
            };
            System.out.println(sb.toString().trim());
        }
    }
}