24
\$\begingroup\$

Alternatively, guess who's doing a course on operating systems

Round Robin scheduling is a way to schedule ready processes in an operating system. Each process in the queue is run for a certain amount of time (quantum), interrupted after that time (if not yet finished), and then added back to the ready queue for another round.

Your task today is to print the order that tasks are executed in a round robin simulation.

The Challenge

Given a list of [int, int] (both > 0), as well as a quantum, return a list of int representing the order that processes were executed. Assume that all the processes arrive at the same time.

The list of [int, int] represents a (simplified) list of processes. The two ints are the process id and service time (the time the process needs to fully run).

For example:

[[1, 5], [2, 10], [3, 3], [4, 12]]

Represents the following processes

Process ID Service Time
1 5
2 10
3 3
4 12

The quantum is an integer > 0 that represents the time slice dedicated to each process. A quantum of 4 means that each process is executed for 4 time units before being interrupted and then added to the ready queue.

If a quantum is larger than the time left on a process, then the next process is selected after the running process ends.

Worked Example

Using the above process list ([[1, 5], [2, 10], [3, 3], [4, 12]]), and a quantum of 4, the process execution order will be:

t = 0
             (head)     (tail)
ready queue = [1, 2, 3, 4]
time left = [5, 10, 3, 12]
Select process 1 to run for 4 time units

t = 4
interrupt process 1
              (head)  (tail)
ready queue = [2, 3, 4, 1]
time left = [10, 3, 12, 1]
Select process 2 to run for 4 time units.

t = 8
interrupt process 2
              (head)   (tail)
ready queue = [3, 4, 1, 2]
time left = [3, 12, 1, 6]
Select process 3 to run for 3 time units

t = 11
process 3 finished
             (head)  (tail)
ready queue = [4, 1, 2]
time left = [12, 1, 6]
Select process 4 to run for 4 time units

t = 15
interrupt process 4
             (head)  (tail)
ready queue = [1, 2, 4]
time left = [1, 6, 8]
Select process 1 to run for 1 time unit

t = 16
process 1 finished
              h    t
ready queue = [2, 4]
time left = [6, 8]
Select process 2 to run for 4 time units

t = 20
interrupt process 2
              h     t
ready queue = [4, 2]
time left = [8, 2]
Select process 4 to run for 4 time units

t = 24
interrupt process 4
              h     t
ready queue = [2, 4]
time left = [2, 4]
Select process 2 to run for 2 time units

t = 26
process 2 finished
              h    t
ready queue = [4]
time left = [4]
Select process 4 to run for 4 time units

t = 30
process 4 finished
no more proceses in the queue.

Therefore, the order of processes executed is:

[1, 2, 3, 4, 1, 2, 4, 2, 4]

Rules

  • Input can be taken as list[list[int, int]], int, list[int], list[int], int, or some other reasonable input method.
  • The processes and quantum can be taken in any order.
  • For example:
list[int: processIds]
list[int: serviceTimes]
int: quantum

or

list[int: serviceTimes]
int: quantum
list[int: processIds]

or any other combination.

  • Output can be list[int], str (joined on newlines, or spaces, or any constant delimiter) or some other reasonable output method.
  • There will always be at least one process.
  • The process ids list will always be a permutation of the range [1, number of processes].
  • The process ids can be 0-indexed if you want it to be for some reason. Using 0-indexing, the ids list will always be a permutation of the range [0, number of processes].
  • The order of the process ids list is important - processes are executed in the order they arrive (in a first come first serve manner). That is how the ready queue in an actual RR simulation works after all (FCFS selection strategy, with pre-emption on time quantums).

Test Cases

processes, times, quantum => order
[1, 2, 3, 4], [5, 10, 3, 12], 4 => [1, 2, 3, 4, 1, 2, 4, 2, 4]
[5, 4, 3, 2, 1], [20, 20, 20, 20, 20], 4 => [5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5], [3, 3, 3, 3, 8], 4 => [1, 2, 3, 4, 5, 5]
[1, 2, 3, 4, 5], [3, 3, 10, 3, 8], 2 => [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 5, 3, 5, 3]
[1], [20], 5 => [1, 1, 1, 1]
[1], [19], 4 => [1, 1, 1, 1, 1]

This is , so the shortest answer in each language wins.

\$\endgroup\$
4
  • \$\begingroup\$ For N processes, are the process IDs guaranteed to be from 1 to N? If yes, are we allowed to take them 0-indexed instead? \$\endgroup\$
    – Arnauld
    Sep 9, 2023 at 23:35
  • 1
    \$\begingroup\$ You can use 0-indexed, yes. It'll be guaranteed that every number in the range [1, N] (or [0, N) if 0-indexed) will be present, but it may not be sorted. \$\endgroup\$
    – lyxal
    Sep 9, 2023 at 23:40
  • \$\begingroup\$ Ah oops my bad. I've corrected it now \$\endgroup\$
    – lyxal
    Sep 9, 2023 at 23:47
  • 1
    \$\begingroup\$ Wow, it's my research area! \$\endgroup\$
    – isaacg
    Sep 11, 2023 at 17:32

21 Answers 21

7
\$\begingroup\$

Jelly, 7 bytes

÷Ċ⁵x"ZẎ

A full program that accepts Times Quantum ProcessIds and prints the schedule.

Try it online!

How?

÷Ċ⁵x"ZẎ - Main Link: Times, Quantum
÷       - {Times} divided by {Quantum}
 Ċ      - ceiling -> {SlotCounts}
  ⁵     - program's third argument -> ProcessIds
    "   - {ProcessIds} zip {SlotCounts} with:
   x    -   {ProcessId} times {SlotCount}
     Z  - transpose
      Ẏ - tighten
        - implicit print
\$\endgroup\$
5
\$\begingroup\$

APL(Dyalog Unicode), 17 bytes SBCS

{0~⍨,⍉↑⍺/⍨¨⌈⍵÷⍺⍺}

Try it on APLgolf!

An operator that takes the quantum as ⍺⍺, times as right argument and 1-indexed process ids as left argument .

⌈⍵÷⍺⍺ times divided by quantum, rounded up.
⍺/⍨¨ For each result, make a vector with the corresponding process id repeated that many times.
Join the vectors into a rectangular matrix, padding shorter vectors with 0s.
,⍉ Transpose matrix, then flatten into vector.
0~⍨ Remove 0s from vector.

\$\endgroup\$
5
\$\begingroup\$

Excel, 45 bytes

=TOCOL(IF(A2#-A3*(ROW(1:99)-1)>0,A1#,NA()),2)

Quantum in cell A3, Process IDs and Service Times in spilled, horizontal ranges A1# and A2# respectively.

Returns a vertical array.

\$\endgroup\$
1
  • \$\begingroup\$ Using Excel always feels like cheating, but this definitely works 😂 \$\endgroup\$ Sep 12, 2023 at 21:33
4
\$\begingroup\$

K (ngn/k), 46 bytes

{2*:'/-1_(#:){(1_y),(0<*|x)#,x:(*y)-0,x}[x]\y}

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ {(*+y)@*|+@/1<:\,/(!'-_-(*|+y)%x),\:'!#y} saves bytes but is not as nice somehow. \$\endgroup\$
    – doug
    Sep 10, 2023 at 6:36
4
\$\begingroup\$

Headass, 58 bytes

U{R])]O:]-[};{N)UO}:NE.UO[N):-E;UP^U][{N)UO}:](>):DOD]O;NE

Takes input as a list like quantum, id_1, servicetime_1, id_2, servicetime_2... with each argument on a separate line. I've gone ahead and made links for each individual test case because I know it's a bit cumbersome to translate.

Test case 1 Test case 2 Test case 3 Test case 4 Test case 5 Test case 6

Explanation:

Pretty straightforward, just subtracts the quantum from each service time, checks if the service time has been used up, and decides whether to keep the values on the queue.

U{R])]O:]-[};{N)UO}:NE.  code block 0
U                        take quantum (q)
 {R])]O:]-[};            negate q and store on queue:
 {         }             loop
  R])                      if q + r2 == 0
     ]O                      store r2 on queue
       :    ;                break from loop
                           else
        ]-[                  decrement r2
                         end loop  
             {N)UO}:     store the remaining inputs on the queue:
             {N)  }:     while there are still inputs
                UO         store input on queue
                    NE   go to code block 1
                      .  end code block

UO[N):-E;UP^U][{N)UO}:](>):DOD]O;NE  code block 1
UO                                   keep q at top of queue
  [                                  r2 = q
   N):                               if there are no items left on the queue
      -E                               go to block -1 (error, halt)
        ;                            endif
         UP                          print the id on top of queue
           ^                         r1 = id
            U][                      r2 = remaining service time + r2
               {N)UO}:               retain remaining values on the queue
                      ](>):          if r2 > 0
                           DO          put r1 on bottom of queue
                             D]O       put r2 on bottom of queue
                                ;    endif
                                 NE  go to code block 1
\$\endgroup\$
2
  • 2
    \$\begingroup\$ why is it called Headass, if I may ask? \$\endgroup\$
    – Jonah
    Sep 11, 2023 at 3:20
  • 1
    \$\begingroup\$ @Jonah I definitely had brainfuck in mind when designing it (for some reason), so I went for something similar: brain -> head (synonym), profanity -> profanity. Any other associations with the name to how the language functions are coincidental, for better or worse. If it were a better language I'd feel worse for giving it such a dumb name :-) \$\endgroup\$ Sep 11, 2023 at 14:57
4
\$\begingroup\$

Vyxal, 44 bitsv2, 5.5 bytes

/⌈$ẋ∩f

Try it Online!

How?

Port of my Jelly answer.

/⌈$ẋ∩f - [Quantum, Times, ProcessIds]
/      - divide -> [Times/Quantum, ProcessIds]
 ⌈     - ceil -> [SlotCounts, ProcessIds]
  $    - swap -> [ProcessIds, SlotCounts]
   ẋ   - repeat -> [RepeatedProcessIds]
    ∩  - transpose -> [ProcessIdSublists]
     f - flatten -> [Schedule]
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 23 21 bytes

-2 bytes from @Bubbler's improvement

{y[&r]@<,/!'r:-_-z%x}

Try it online!

Takes three arguments, x (quantum), y (processes), and z (times).

Based on @frasiyav's BQN answer.

  • r:-_-z%x calculate the ceiling of the times (z) divided by the quantum (x), and store it in variable r
  • <,/!' generate 0..r-1 for each value in r, flatten them into a list, and then grade-up them (this is related to an "occurrence count")
  • y[&r]@ use this to index into a list containing the correct number of copies of each process ID
\$\endgroup\$
1
  • 1
    \$\begingroup\$ {y[&r]@<,/!'r:-_-z%x} is 2 bytes shorter. \$\endgroup\$
    – Bubbler
    Oct 27, 2023 at 5:22
3
\$\begingroup\$

J, 21 bytes

(/:1#.]=]\)@#~>.@%&>/

Attempt This Online!

The Jelly / APL transpose approach was too verbose in J so I found a sorting based approach. Consider this example 1 2 3 4 f 5 10 3 12 ; 4:

  • >.@%&>/ It starts the same as the APL approach dividing the times by the quantum and taking the ceiling:

    2 3 1 3
    
  • #~ It uses that mask to duplicate the process ids in place:

    1 1 2 2 2 3 4 4 4
    
  • (/: )@ Now we finish by applying a single sort... we just need to find the correct ordering...

  • ]=]\ This creates the prefix lists with zero fill on the right, and then asks, "Where does each element equal that value?" Thus each element is compared to a row:

    1 0 0 0 0 0 0 0 0
    1 1 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0
    0 0 1 1 0 0 0 0 0
    0 0 1 1 1 0 0 0 0
    0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 1 0
    0 0 0 0 0 0 1 1 1
    
  • 1#. Now when we sum each row we get a running count of how many times each element has appeared so far:

    1 2 1 2 3 1 1 2 3
    

    This is exactly the ordering we need to achieve the round robin.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 56 bytes

f@q_=#&@@@Flatten[#~Partition~UpTo@q&/@Table@@@#,{2,1}]&

Try all test cases online. Defines a function named f that takes its arguments in a format like (for the first test case) f[4][{{1,5},{2,10},{3,3},{4,12}}]. The code isn't all that short, but I learned something about Flatten that made me want to share this approach. Using the first test case:

  • Table@@@# evaluates to { {1,1,1,1,1}, {2,2,2,2,2,2,2,2,2,2}, {3,3,3}, {4,4,4,4,4,4,4,4,4,4,4,4} }.
  • #~Partition~UpTo@q& operates on each element of that list, yielding { { {1,1,1,1}, {1} }, { {2,2,2,2}, {2,2,2,2}, {2,2} }, { {3,3,3} }, { {4,4,4,4}, {4,4,4,4}, {4,4,4,4}, {4,4,4,4} } }.
  • Next we want to transpose this array (an array in which each element is a short constant list of length at most 4); but Transpose doesn't handle ragged lists—the idiom for that in Mathematica is Flatten[#,{2}]. This would yield { { {1,1,1,1}, {2,2,2,2}, {3,3,3}, {4,4,4,4} }, { {1}, {2,2,2,2}, {4,4,4,4} }, { {2,2}, {4,4,4,4} }, { {4,4,4,4} } }.
  • It turns out that we want to partially flatten this resulting list as well; so we could apply Flatten[#,{1}] to it (we could've also applied Join suitably). Now here's the cool bit I never realized before: Flatten[#,{2,1}] will cheerfully flatten the list first at the second level and then at the first level—in that "wrong" order! The result is { {1,1,1,1}, {2,2,2,2}, {3,3,3}, {4,4,4,4}, {1}, {2,2,2,2}, {4,4,4,4}, {2,2}, {4,4,4,4}, {4,4,4,4} }.
  • Now all that's left is to take the first element of each list (using #&@@@), which gives { 1, 2, 3, 4, 1, 2, 4, 2, 4, 4 }.
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 57 bytes

Expects (serviceTimes)(quantum)(processIds), using 0-indexed process IDs. Returns a space-separated string.

t=>q=>g=([n,...p])=>1/n?n+' '+g((t[n]-=q)>0?[...p,n]:p):p

Try it online!

Commented

t =>            // t[] = array of service times
q =>            // q = quantum
g = ([          // g is a recursive function taking:
  n,            //   n = ID of next process
  ...p          //   p[] = array of remaining process IDs
]) =>           //
1 / n ?         // if n is defined:
  n + ' ' +     //   append n followed by a space
  g(            //   followed by the result of a recursive call:
    (t[n] -= q) //     subtract q from the n-th service time
    > 0 ?       //     if the result is positive:
      [...p, n] //       still running: put back n at the end of p[]
    :           //     else:
      p         //       kill the process by just passing p[]
  )             //   end of recursive call
:               // else:
  p             //   stop the recursion (p[] is now empty)
\$\endgroup\$
0
3
\$\begingroup\$

BQN, 16 bytes

{⍋∘⊒⊸⊏⌈∘÷⟜𝕨⊸/˝𝕩}

Try it here.

Takes the quantum as the left argument 𝕨 and an array of [serviceTimes, processIds] as the right argument 𝕩.

How it works:

{⍋∘⊒⊸⊏⌈∘÷⟜𝕨⊸/˝𝕩}
             ˝𝕩  # Apply between rows of the right argument:
           ⊸/    #   replicate the ids by 
      ⌈∘÷⟜𝕨      #   the ceil of serviceTimes divided by the quantum.
    ⊸⊏           # Then, reorder the result according to:
   ⊒             #   the running occurrence count
 ⍋∘              #   graded by ascending order.
\$\endgroup\$
2
\$\begingroup\$

sclin, 17 bytes

/ |^"*`"zip tpose

Try it on scline! Way simpler than I thought...

Explanation

  • / |^ Divide each service time by quantum and round up
  • "*`"zip repeat each process number by previous results
  • tpose transpose - this fortunately works with uneven lists-of-lists!

sclin, 54 bytes

=$n.
dups"; @"&#
1_ roll0.: Q n>o0$n , -1.: Q0>"pop"|#

Try it on scline! Initial solution.

Explanation

Prettified code:

=$n.
dups ( ; @ ) &#
  1_ roll 0.: Q n>o 0 $n , - 1.: Q 0> \pop |#

Takes processes input as a list of [int int].

  • =$n quantum as n
  • dups ( ; @ ) &# if stack is not empty, execute next line and loop...
    • 1_ roll rotate bottom of stack to the top
    • 0.: Q n>o output process number
    • 0 $n , - decrement service time by n
    • 1.: Q 0> \pop |# if service time <= 0, then pop from the stack
\$\endgroup\$
2
\$\begingroup\$

Python, 61 bytes

lambda q,i:[I for Q in range(max(i)[0])for C,I in i if C>q*Q]

Attempt This Online!

Expects quantum,list of cost-id pairs.

How?

Instead of updating the remaining cost in each pair we run through the unchanged list repeatedly and after each cycle update the threshold (0,q,2q,3q,...) by which processes are filtered.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 23 bytes

F⌈Eθ§ι¹IEΦθ››§κ¹ι﹪ιη§κ⁰

Try it online! Link is to verbose version of code. Takes input as a list of pairs of (process id, service time) and the quantum. Explanation:

F⌈Eθ§ι¹

Loop up to the maximum service time.

IEΦθ››§κ¹ι﹪ιη§κ⁰

Output any processes due to be serviced at this time (i.e. their service time is higher and this is actually a multiple of the quantum.)

Would be 17 bytes if dictionary order was guaranteed:

F⌈EθιIEΦθ››κι﹪ιηλ

Attempt This Online! Link is to verbose version of code. Takes input as a dictionary and a number. Explanation:

F⌈Eθι

Loop up to the maximum service time.

IEΦθ››κι﹪ιηλ

Output any processes due to be serviced at this time (i.e. their service time is higher and this is actually a multiple of the quantum.)

\$\endgroup\$
3
  • \$\begingroup\$ > Input can be taken as list[list[int, int]], int...or some other reasonable input format \$\endgroup\$
    – lyxal
    Sep 10, 2023 at 7:53
  • \$\begingroup\$ Your 23 byter is valid as taking int int pairs is perfectly fine. \$\endgroup\$
    – lyxal
    Sep 10, 2023 at 7:53
  • \$\begingroup\$ @lyxal Thanks, I had overlooked that. \$\endgroup\$
    – Neil
    Sep 10, 2023 at 8:49
2
\$\begingroup\$

Scala 3, 72 bytes

A port of @loopy walt's Python answer in Scala.


Golfed version. Attempt This Online!

(q,i)=>(for{Q<-0 to i.map(_._1).max-1;p<-i;if p._1>q*Q}yield p._2).toSeq

Ungolfed version. Attempt This Online!

def f(q: Int, i: List[(Int, Int)]): List[Int] = {
    val maxC = i.maxBy(_._1)._1
    (for {
      Q <- 0 until maxC
      pair <- i
      if pair._1 > q * Q
    } yield pair._2).toList
}
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 9 bytes

/îδиÅ\ζ˜þ

-1 thanks to Kevin Cruijssen

Try it online!

\$\endgroup\$
2
2
\$\begingroup\$

Retina 0.8.2, 76 75 bytes

\d+(?=,|$)
$*#
(?=.*, (#)+)(?<-1>#)+
@
S`, 
rM!&`.+@
O$^`.+: (@+)
$1_
: @+

Try it online! Link includes test cases. Takes input as a list of pairs and an integer. Explanation:

\d+(?=,|$)
$*#

Convert the durations to unary.

(?=.*, (#)+)(?<-1>#)+
@

Calculate the number of times each process gets scheduled.

S`, 

Split each process to its own line.

rM!&`.+@

Match each process once for each tick. This has to be done in reverse for the overlapping matches to work properly, so the processes actually come out in the wrong order.

O$^`.+: (@+)
$1_

Sort them according to the tick count and fix up the ordering.

: @+

Delete the tick counts.

(Out of interest I did try a repeat/transpose/flatten approach but the best I could do in Retina 1 was 79 bytes.)

\$\endgroup\$
2
\$\begingroup\$

Uiua, 11 bytes

▽±.♭⍉⬚0≡↯⌈÷

Try it online!

▽±.♭⍉⬚0≡↯⌈÷    input: quantum, times, IDs
            ⌈÷     divide times by quantum and take ceiling -> occurrence count
        ⬚0≡↯      duplicate each ID that many times forming a row in a matrix,
                   padding short rows with zeros
                   for the first example, [[1,1,0], [2,2,2], [3,0,0], [4,4,4]]
    ♭⍉           transpose and flatten
▽±.               keep nonzero elements

Some 12- and 13-byte solutions:

⊏⍏⊐/⊂⊃⊐∵⇡▽⌈÷   # 12
               ⌈÷    same as the above
       ⊃            run two functions over two stack items(repetitions, ids):
   ⊐/⊂  ⊐∵⇡       ranges of repetitions concatenated; [0, 1, 0, 1, 2, 0, 0, 1, 2]
             ▽      duplicate each ID in a vector; [1, 1, 2, 2, 2, 3, 4, 4, 4]
⊏⍏                 reorder the IDs by the ascending order of the ranges

⊏⍏-⊗⊃.⍏⊃⊚▽⌈÷  # 12
⊏⍏        ⊃ ▽⌈÷    same as above
            ⊚        duplicate indices by values; [0, 0, 1, 1, 1, 2, 3, 3, 3]
    ⊗⊃.⍏           self-index and sorting order: [0, 0, 2, 2, 2, 5, 6, 6, 6],
                      [0, 1, 2, 3, 4, 5, 6, 7, 8]
   -                  subtract first from second: [0, 1, 0, 1, 2, 0, 0, 1, 2]

⊏⍏⍜⊕□⊐≡⍏..▽⌈÷   # 13
⊏⍏          .▽⌈÷     same as above, but using just duplicated ids
   ⍜⊕□⊐≡⍏.          group by itself and replace each group with range of that length
\$\endgroup\$
1
\$\begingroup\$

Python3, 83 bytes:

def R(p,t,q):
 Q,s=[*zip(p,t)],[]
 for a,b in Q:s+=[a];Q+=[(a,b-q)]*(b>q)
 return s

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ (b-q>0) is (b>q) \$\endgroup\$
    – Arnauld
    Sep 10, 2023 at 0:20
  • \$\begingroup\$ @Arnauld Thank you, updated \$\endgroup\$
    – Ajax1234
    Sep 10, 2023 at 0:59
1
\$\begingroup\$

AWK, 68 bytes

a=$1{for(b=1;b<NF;){$++c=$++b;if(0<d=$++b-c){$++NF=$c;$++NF=d}}}NF=c

Try it online!

This program expects the first commandline argument to give the quantum. And the arguments after that are pairs of pid/service-time values. It works by iterating through the pid/time pairs, adding the pid to an output list. Then if the service time remaining is larger than the quantum, the pid and remaining time are appended to the argument. So it essentially extends the commandline arguments as needed. And the "output list" is stored at the beginning of the argument list. Each iteration consumes two values from the argument list but only adds one (the pid) to the front of the argument list. So once the all the arguments have been processed, all that's left to do is set the number of arguments to the size of the output list. The pid list if printed automatically since the "test" that sets the number of arguments has no associated code.

a=$1{ ... }               -- set "a" to the quantum (first arg)
.. for( ... ){ ... }      -- loop to process pairs of args
.. .. b=1;b<NF;           -- stops when at the end of args
.. .. .. $++c=$++b;       -- copy the "pid" to the output list and increment
.. .. .. if( ... ){ ... } -- "true" when service time > quantum
.. .. .. .. 0<d=$++b-c    -- set "d" to remaining service time
.. .. .. .. .. $++NF=$c;  -- append pid to end of args
.. .. .. .. .. $++NF=d    -- append remaining service time
NF=c                      -- set the number of pids to print
\$\endgroup\$
1
\$\begingroup\$

C++ (gcc), 97 93 bytes

[](auto&l,int q,auto o){for(int m;m=0,q;q=m<q?m:q)for(auto&[p,t]:l)m=t>m?t:m,t>0?o=p:o,t-=q;}

Try it online!

4 bytes shaved off thanks to ceilingcat. Takes a list of pairs as input, and uses an insert iterator to return the results. Explanation:

[](auto& l, int q, auto o) {   // Process list, quantum, output iterator
    for (int m; m = 0,         // Will track maximum time of all processes
           q;                  // As long as quantum is still non-zero
           q = m < q ? m : q)  // Limit quantum to the maximum process time
       for (auto& [p, t]: l)   // Loop over all processes
           m = t > m ? t : m,  // Update the maximum time
           t > 0 ? o = p : o,  // Output process number if time left is positive
           t -= q;             // Subtract the quantum from the time
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.