Question

Input (stdin)

Josefine is in charge of the local student organization at The University of Algorithms. The organization gets tasks they must complete. Each task has a unique id and a unique difficulty. Over time new tasks are given to the organization, and Josefine is then responsible for delegating these to the members of the organization. When a member is ready to do a new task, he/she asks Josefine for a new task. Josefine likes to challenge her members, so she always pick the most difficult currently available task when a member requests a new task Help Josefine write a program that decides what task to give to a member when they request a new task. Input format Line 1: The integer N that is the total number of new and requested tasks (0 N 1.000.000). Line 2.N+1: Either: got a new task with the given id and dificulty (O S id.,dificuity S 1.000.000), "R' corresponding to a member is ready to receive a "N id difficulty" coresponding to the organization new task. Output format Line i: The id of the task given to the ith receive request.

7

N 4 5

N 9 6

N 16 3

R

N 12 8

R

R

Expected Output

9

12

4

Make it in java

Answer 1

We can follow a simple approach here, to solve this problem.

For a given input, there are two possibilities:

1. Whenever a new task is assigned to the organization, we simply store the unique id, unique difficulty values associated with the task, into our data structure. (input is: N id difficulty)

2. When a member is ready to do a task, we pick the task with highest difficulty value, from our data structure, print the id of that task onto the screen, and remove that task form our data structure. ( input is: R )

The data structure used here is TreeMap.

so, what is TreeMap?

TreeMap stores the data in key, value pair. Each record is stored in <key, value> format. It provides an efficient means of sorting the <key, value> pair, in sorted order.

For our solution, we need the difficulty value of the task to be sorted. so, I have used the difficulty value as the key, and the Task id as value.

Java code:

import java.util.Scanner; // To scan input from standard input(Key Board)
import java.util.TreeMap; // To use the Tree Map data structure
import java.util.Collections; //To sort the data in descending order of difficulty level.

public class Main {

public static void main(String[] args) {

/* create an object of TreeMap which stores 2 integers as key, value pairs. Difficulty value and Task id. Comparator is used to sort the key values in descending order. The default order is Ascending order. */

TreeMap<Integer, Integer> treemap = new TreeMap<Integer, Integer>(Collections.reverseOrder());
Scanner scanner = new Scanner(System.in).useDelimiter("\n"); //delimiter is used to scan input string along with spaces
int t = scanner.nextInt(); //scan number of inputs
while(t > 0) {
t--;
String input = scanner.next(); //scan the actual string
char c = input.charAt(0); //taking first character from input provided and checking for new task.

// if block is executed, when we wish to assign a difficult task to a user.
if(c == 'R') {   

if( treemap.isEmpty() ) // checking if there are any tasks present
System.out.println("No task is present to assign");

else {   
Integer op = treemap.firstKey(); // taking the difficult task, present on top, as TreeMap is sorted.
  Integer assignid = treemap.remove(op); // Removing task, as it is assigned to a person. It returns task id
System.out.println(assignid); // displaying the id.

}
}

// else block is executed, when a new task is given to organization
else {

  /* breaking the input when space is encountered. This gives us three strings. First String is "N". Second and Third Strings represent Task id and Task Difficulty level */
String[] splited = input.split("\\s+"); // split using regular expression
Integer id = Integer.valueOf(splited[1]); //Task id
Integer strength = Integer.valueOf(splited[2]); // task difficulty
treemap.put(strength, id); // inserting in treemap with difficulty as key, and Task id as value.
}
  
} // end of while loop
scanner.close();
} // end of main function
} //end of class

Output for the given input:

9

12

4

This code works fine, for any given input. There will be no problem with similar keys, because it is mentioned that unique task difficulty is present. This program also prints a message saying "No Task is present to assign" when there are no tasks present with the organization, to assign tasks to its members.