Connection Status:
Competition Arena > Messaging

Messaging

Rookie SRM 16 · 2022-08-22 · by lars2520

Rookie SRM 16 · 2022-08-22 · by lars2520 · Graph Theory
Class Name: Messaging
Return Type: String
Method Name: getNext
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

In many systems, there is a need for some sort of messaging service between various components of the system. The most common type of messaging service is probably first in/first out queue, meaning that the messages get sent out in the order that they are received. However, different messages often have different priorities, and in our service, whenever we send out a message, we want to send out the message with the highest priority. In this problem, you are to simulate this queue. You will be given a String[], messages, representing a number of messages that are sent to the queue. Each element of messages will be in the format "<message> <priority> <time>", where <message> is a string of lowercase letters ('a'-'z'), <priority> is an integer representing the priority of the message, and <time> is the time that the message was received, in seconds since the system was started. The messaging service is able to send out one message every second, if there is one in the queue. The queue may also send out a message the same second it comes in.
Your task is to model this messaging service. In addition to messages, you will be given an int, time, representing the number of seconds since the system was started. Your task is to determine which message the service sends at that second and return a String representing the message sent out. If no message is sent out at time, then you should return the empty String, "".

Notes

  • Note that, to make things simpler, each priority is distinct.

Constraints

  • messages will contain between 0 and 50 elements, inclusive.
  • Each element of messages will contain between 5 and 50 characters, inclusive.
  • Each element of messages will be formatted as "<message> <priority> <time>".
  • <message> will be a sequence of 1 or more lowercase letters ('a'-'z').
  • <priority> will be an integer with no leading zeros, between 1 and 100, inclusive.
  • Each <priority> will be distinct.
  • <time> will be an integer with no extra leading zeros between 0 and 1000, inclusive.
  • time will be between 0 and 2000, inclusive.
  • Elements of messages will be sorted in non-decreasing order, by time.
Examples
0)
{"hello 1 1","how 4 1","are 2 3","you 5 4"}
1
Returns: "how"

At time = 1, both "hello" and "how" are added to the queue. Of these, "how" has the higher priority, so it is sent.

1)
{"hello 1 1","how 4 1","are 2 3","you 5 4"}
2
Returns: "hello"

At time = 2, no new messages arrive, so the remaining message from time 1 is sent.

2)
{"hello 1 1","how 4 1","are 2 3","you 5 4"}
3
Returns: "are"

At time = 3, the queue starts out empty, and then receives a single message, "are". Since there is only one message in the queue to send, it is sent on.

3)
{"hello 1 1","how 4 1","are 2 3","you 5 5"}
4
Returns: ""

At time = 4, the queue is empty.

4)
{"priority 9 1",
"be 3 1",
"queues 5 2",
"can 4 3",
"implemented 1 3",
"but 8 7",
"in 11 7",
"would 2 7",
"nlogn 12 8",
"yours 21 10",
"that 10 10",
"slower 18 10",
"than 14 11",
"can 75 11",
"be 50 11",
"much 42 13",
"be 30 30"}
14
Returns: "slower"

Here is what the queue would send at each time step. (Note the hint and don't try to implement a heap) Time | Message sent ('_' means no message was sent) -----+-------------- 0 | _ 1 | priority 2 | queues 3 | can 4 | be 5 | implemented 6 | _ 7 | in 8 | nlgn 9 | but 10 | yours 11 | can 12 | be 13 | much 14 | slower 15 | that 16 | than 17 | would 18 | _ ... | _ 30 | be

Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Messaging with a public method string getNext(vector<string> messages, int time) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous