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

題目描述

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

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

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

擁有最高累計學業成績平均點數(CGPA)的學生會最先被服務。
擁有相同累計學業成績平均點數(CGPA)的學生們會使用他們的名字字典順序來排序,並區分大小寫。
擁有相同累計學業成績平均點數(CGPA)和名字的學生們會使用進入佇列的記號來排序

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

原題網址

https://www.hackerrank.com/challenges/java-priority-queue

輸入格式

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

ENTER name CGPA token:將學生排入佇列。
SERVED:佇列中擁有最高優先權而被服務的學生。

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

輸出格式

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

範例輸入

12
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

範例輸出

Dan
Ashley
Shafaet
Maria

額外解釋

ENTER John 3.75 50:

John 3.75 50

ENTER Mark 3.8 24:

John 3.75 50
Mark 3.8 24

ENTER Shafaet 3.7 35:

Mark 3.8 24
John 3.75 50
Shafaet 3.7 35

SERVED:

John 3.75 50
Shafaet 3.7 35

SERVED:

Shafaet 3.7 35

ENTER Samiha 3.85 36:

Samiha 3.85 36
Shafaet 3.7 35

SERVED:

Shafaet 3.7 35

ENTER Ashley 3.9 42:

Ashley 3.9 42
Shafaet 3.7 35

ENTER Maria 3.6 46:

Ashley 3.9 42
Shafaet 3.7 35
Maria 3.6 46

ENTER Anik 3.95 49:

Anik 3.95 49
Ashley 3.9 42
Shafaet 3.7 35
Maria 3.6 46

ENTER Dan 3.95 50:

Anik 3.95 49
Dan 3.95 50
Ashley 3.9 42
Shafaet 3.7 35
Maria 3.6 46

SERVED:

Dan 3.95 50
Ashley 3.9 42
Shafaet 3.7 35
Maria 3.6 46

解題概念

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

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

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章