Task Manager (Priority Queue)

Task Manager (Priority Queue)

Hard PHP PHP OOP Basics 32 views
Explanation Complexity

Problem Statement

Commands: ADD name p, POP. POP removes and prints the task with highest priority; if tie, the one added earlier. If empty, print EMPTY.

Input Format

First line q. Next q lines.

Output Format

Outputs for POP.

Example

7
POP
ADD clean 2
ADD build 5
ADD test 5
POP
POP
POP
EMPTY
build
test
clean

Constraints

q

Input / Output Format

Input Format
First line q. Next q lines.
Output Format
Outputs for POP.
Constraints
q

Examples

Input:
7 POP ADD clean 2 ADD build 5 ADD test 5 POP POP POP
Output:
EMPTY build test clean

Example Solution (Public)

PHP 
<?php
class TaskManager{
  private $queue;
  private $order=0;
  function __construct(){
    $this->queue=new SplPriorityQueue();
    $this->queue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
  }
  function addTask($name,$priority){
    $this->queue->insert($name, [$priority, -$this->order]);
    $this->order++;
  }
  function popTask(){
    if($this->queue->isEmpty()) return null;
    return $this->queue->extract();
  }
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$q=intval($inputLines[0]);
$tasks=new TaskManager();
$output=[];
for($lineNo=1;$lineNo<=$q;$lineNo++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$lineNo] ?? ''));
  $cmd=$tokens[0] ?? '';
  if($cmd==='ADD'){
    $tasks->addTask($tokens[1] ?? '', intval($tokens[2] ?? 0));
  }else{
    $name=$tasks->popTask();
    $output[] = ($name===null) ? 'EMPTY' : $name;
  }
}
echo implode(PHP_EOL,$output);
?>

Official Solution Code

<?php
class TaskManager{
  private $queue;
  private $order=0;
  function __construct(){
    $this->queue=new SplPriorityQueue();
    $this->queue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
  }
  function addTask($name,$priority){
    $this->queue->insert($name, [$priority, -$this->order]);
    $this->order++;
  }
  function popTask(){
    if($this->queue->isEmpty()) return null;
    return $this->queue->extract();
  }
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$q=intval($inputLines[0]);
$tasks=new TaskManager();
$output=[];
for($lineNo=1;$lineNo<=$q;$lineNo++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$lineNo] ?? ''));
  $cmd=$tokens[0] ?? '';
  if($cmd==='ADD'){
    $tasks->addTask($tokens[1] ?? '', intval($tokens[2] ?? 0));
  }else{
    $name=$tasks->popTask();
    $output[] = ($name===null) ? 'EMPTY' : $name;
  }
}
echo implode(PHP_EOL,$output);
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.