Statistics

Problem Statement for "RRSchedule"

Problem Statement

When multiple tasks are executed on a single CPU, they are not truly run in parallel. Instead, the CPU spends some time on each task in turn, and a scheduler is used to decide which task to run at any given time. Real-world schedulers are quite complex and must try to balance conflicting priorities.

For the purposes of this problem, we will consider only a simple "round-robin" scheduler. There are N tasks, numbered 0 to N-1. The scheduler runs each task in turn for one second, starting with task 0 and proceeding with tasks 1, 2, ..., N-1, before starting again at 0. Once a task completes executing, the scheduler will skip over that task in the future.

Element i of tasks is the number of seconds of execution time required by task i. Return a int[] containing exactly N integers, where the i-th element is the total time the system has been running when task i completes.

Definition

Class:
RRSchedule
Method:
terminalTimes
Parameters:
int[]
Returns:
int[]
Method signature:
int[] terminalTimes(int[] tasks)
(be sure your method is public)

Constraints

  • tasks will contain between 1 and 50 elements, inclusive.
  • Each element of tasks will be between 1 and 20,000,000, inclusive.

Examples

  1. {2, 1, 2, 4}

    Returns: {5, 2, 6, 9 }

    For the first four seconds, each task gets one turn, and the 2nd task completes after 2 seconds. The next two seconds complete the first and third tasks, and three more seconds are required to complete the fourth task.

  2. {1, 2, 3}

    Returns: {1, 4, 6 }

  3. {3, 2, 2, 1}

    Returns: {8, 6, 7, 4 }

  4. {2, 4, 7, 7, 3, 2, 9, 10, 5, 8, 10, 1, 5, 7, 6, 8, 10, 4, 9, 7, 10, 4, 3, 9}

    Returns: {25, 69, 118, 119, 51, 30, 140, 147, 92, 133, 148, 12, 95, 124, 111, 135, 149, 82, 144, 128, 150, 86, 67, 146 }

  5. {1}

    Returns: {1 }

  6. {20000000}

    Returns: {20000000 }

  7. {5, 5}

    Returns: {9, 10 }

  8. {5, 4}

    Returns: {9, 8 }

  9. {5, 6}

    Returns: {9, 11 }

  10. {1, 2, 2, 3, 1, 3, 2, 20000000}

    Returns: {1, 9, 10, 15, 5, 16, 13, 20000014 }

  11. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}

    Returns: {1, 51, 100, 148, 195, 241, 286, 330, 373, 415, 456, 496, 535, 573, 610, 646, 681, 715, 748, 780, 811, 841, 870, 898, 925, 951, 976, 1000, 1023, 1045, 1066, 1086, 1105, 1123, 1140, 1156, 1171, 1185, 1198, 1210, 1221, 1231, 1240, 1248, 1255, 1261, 1266, 1270, 1273, 1275 }

  12. {99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50}

    Returns: {3725, 3724, 3722, 3719, 3715, 3710, 3704, 3697, 3689, 3680, 3670, 3659, 3647, 3634, 3620, 3605, 3589, 3572, 3554, 3535, 3515, 3494, 3472, 3449, 3425, 3400, 3374, 3347, 3319, 3290, 3260, 3229, 3197, 3164, 3130, 3095, 3059, 3022, 2984, 2945, 2905, 2864, 2822, 2779, 2735, 2690, 2644, 2597, 2549, 2500 }

  13. {1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2}

    Returns: {1, 51, 3, 88, 5, 53, 7, 118, 9, 55, 11, 90, 13, 57, 15, 145, 17, 59, 19, 92, 21, 61, 23, 120, 25, 63, 27, 94, 29, 65, 31, 163, 33, 67, 35, 96, 37, 69, 39, 122, 41, 71, 43, 98, 45, 73, 47, 147, 49, 75 }

  14. {20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000}

    Returns: {999999951, 999999952, 999999953, 999999954, 999999955, 999999956, 999999957, 999999958, 999999959, 999999960, 999999961, 999999962, 999999963, 999999964, 999999965, 999999966, 999999967, 999999968, 999999969, 999999970, 999999971, 999999972, 999999973, 999999974, 999999975, 999999976, 999999977, 999999978, 999999979, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985, 999999986, 999999987, 999999988, 999999989, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999, 1000000000 }

  15. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 20000000}

    Returns: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 20000049 }

  16. {20000000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 20000000}

    Returns: {40000047, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 40000048 }

  17. {19999999, 19999998, 19999997, 19999996, 19999995, 19999994, 19999993, 19999992, 19999991, 19999990, 19999989, 19999988, 19999987, 19999986, 19999985, 19999984, 19999983, 19999982, 19999981, 19999980, 19999979, 19999978, 19999977, 19999976, 19999975, 19999974, 19999973, 19999972, 19999971, 19999970, 19999969, 19999968, 19999967, 19999966, 19999965, 19999964, 19999963, 19999962, 19999961, 19999960, 19999959, 19999958, 19999957, 19999956, 19999955, 19999954, 19999953, 19999952, 19999951, 19999950}

    Returns: {999998725, 999998724, 999998722, 999998719, 999998715, 999998710, 999998704, 999998697, 999998689, 999998680, 999998670, 999998659, 999998647, 999998634, 999998620, 999998605, 999998589, 999998572, 999998554, 999998535, 999998515, 999998494, 999998472, 999998449, 999998425, 999998400, 999998374, 999998347, 999998319, 999998290, 999998260, 999998229, 999998197, 999998164, 999998130, 999998095, 999998059, 999998022, 999997984, 999997945, 999997905, 999997864, 999997822, 999997779, 999997735, 999997690, 999997644, 999997597, 999997549, 999997500 }

  18. {20000000, 19999999, 19999999, 19999998, 19999998, 19999997, 19999997, 19999996, 19999996, 19999995, 19999995, 19999994, 19999994, 19999993, 19999993, 19999992, 19999992, 19999991, 19999991, 19999990, 19999990, 19999989, 19999989, 19999988, 19999988, 19999987, 19999987, 19999986, 19999986, 19999985, 19999985, 19999984, 19999984, 19999983, 19999983, 19999982, 19999982, 19999981, 19999981, 19999980, 19999980, 19999979, 19999979, 19999978, 19999978, 19999977, 19999977, 19999976, 19999976, 19999975}

    Returns: {999999375, 999999373, 999999374, 999999370, 999999371, 999999365, 999999366, 999999358, 999999359, 999999349, 999999350, 999999338, 999999339, 999999325, 999999326, 999999310, 999999311, 999999293, 999999294, 999999274, 999999275, 999999253, 999999254, 999999230, 999999231, 999999205, 999999206, 999999178, 999999179, 999999149, 999999150, 999999118, 999999119, 999999085, 999999086, 999999050, 999999051, 999999013, 999999014, 999998974, 999998975, 999998933, 999998934, 999998890, 999998891, 999998845, 999998846, 999998798, 999998799, 999998750 }

  19. {12440, 19600, 3206, 23633, 17648, 15240, 13090, 27420, 22789, 10407, 27402, 11145, 26148, 32037, 17545, 10005, 24948, 31930, 12310, 11874, 905, 19215, 13647, 2682, 28106, 23527, 7605, 30436, 18819, 14860, 3882, 12393, 15561, 20732, 21035, 9379, 20753, 9553, 16333, 3658, 10127, 10225, 4985, 2622, 5968, 4089, 7271, 29012, 4374, 26474}

    Returns: {506958, 666247, 156847, 721452, 630324, 578442, 524513, 754619, 711430, 443943, 754511, 467561, 745406, 769045, 628269, 430338, 734607, 768938, 503247, 490167, 45221, 659710, 539005, 132238, 758052, 720293, 340222, 765950, 652585, 569335, 187746, 505662, 585839, 684371, 688636, 407642, 684688, 414082, 602827, 177674, 434626, 437959, 234784, 129377, 275088, 196867, 327209, 761678, 209125, 748020 }

  20. {2, 3, 4, 3, 4, 2, 4, 2, 4, 2, 4, 3, 2, 4, 4, 1, 1, 4, 4, 3, 1, 1, 1, 1, 2, 2, 4, 2, 1, 2, 3, 2, 1, 3, 3, 3, 1, 4, 3, 4, 4, 1, 2, 2, 2, 3, 3, 1, 1, 3}

    Returns: {51, 89, 114, 91, 115, 56, 116, 58, 117, 60, 118, 96, 63, 119, 120, 16, 17, 121, 122, 101, 21, 22, 23, 24, 69, 70, 123, 72, 29, 73, 103, 75, 33, 104, 105, 106, 37, 124, 108, 125, 126, 42, 83, 84, 85, 111, 112, 48, 49, 113 }

  21. {14790601, 3056401, 13483201, 17755801, 14310601, 13620001, 8140201, 16497601, 18094801, 2110201, 16306201, 1700401, 11173201, 3631201, 3681601, 14924401, 11148601, 13099201, 4647001, 10285201, 12146401, 11496001, 11440201, 14634001, 10753201, 2373601, 17504401, 7675201, 274801, 16221601, 17795401, 5571601, 6424801, 10805401, 14577001, 15642001, 11461801, 18305401, 8432401, 11442601, 16840201, 15165601, 3370801, 8733601, 12734401, 3105001, 5746201, 18059401, 6205201, 13140001}

    Returns: {513699637, 147053406, 492187233, 539302846, 506389836, 494649636, 344481021, 531662444, 540324049, 103264812, 530131245, 83594413, 440722231, 172132818, 174249619, 515439042, 440033432, 484850439, 213831023, 414006631, 464253638, 449294438, 447931236, 511507242, 428514636, 115644627, 538045847, 328206035, 13740029, 529369846, 539461248, 250815034, 283191637, 430080640, 510652245, 523573847, 448473644, 540534650, 354415843, 447993645, 534060649, 518333449, 160935644, 364355447, 477189648, 149240446, 257624447, 540253250, 275066449, 485666450 }

  22. {2, 4, 7, 7, 3, 2, 9, 10, 5, 8, 10, 1, 5, 7, 6, 8, 10, 4, 9, 7, 10, 4, 3, 9 }

    Returns: {25, 69, 118, 119, 51, 30, 140, 147, 92, 133, 148, 12, 95, 124, 111, 135, 149, 82, 144, 128, 150, 86, 67, 146 }

  23. {20000000, 19999999, 19999998, 19999997, 19999996, 19999995, 19999994, 19999993, 19999992, 19999991, 19999990, 19999989, 19999988, 19999987, 19999986, 19999985, 19999984, 19999983, 19999982, 19999981, 19999980, 19999979, 19999978, 19999977, 19999976, 19999975, 19999974, 19999973, 19999972, 19999971, 19999970, 19999969, 19999968, 19999967, 19999966, 19999965, 19999964, 19999963, 19999962, 19999961, 19999960, 19999959, 19999958, 19999957, 19999956, 19999955, 19999954, 19999953, 19999952, 19999951 }

    Returns: {999998775, 999998774, 999998772, 999998769, 999998765, 999998760, 999998754, 999998747, 999998739, 999998730, 999998720, 999998709, 999998697, 999998684, 999998670, 999998655, 999998639, 999998622, 999998604, 999998585, 999998565, 999998544, 999998522, 999998499, 999998475, 999998450, 999998424, 999998397, 999998369, 999998340, 999998310, 999998279, 999998247, 999998214, 999998180, 999998145, 999998109, 999998072, 999998034, 999997995, 999997955, 999997914, 999997872, 999997829, 999997785, 999997740, 999997694, 999997647, 999997599, 999997550 }

  24. {15274004, 19126450, 6798728, 2924584, 477357, 17103516, 18985775, 13482168, 18016791, 12862991, 10809497, 9632009, 14383284, 7670367, 2745334, 7549704, 8172836, 514983, 10755394, 12531286, 4076837, 2420926, 3007793, 12974153, 12171988, 7700620, 5691689, 5681468, 18709995, 15249833, 7488104, 9066909, 5224632, 18584317, 860130, 16024219, 3621803, 13060601, 5679452, 6808763, 8515502, 12464236, 10447503, 4914923, 5651680, 10740098, 16126423, 18080536, 12105582, 8974839 }

    Returns: {468650617, 491942612, 291449039, 138624969, 23867805, 483059839, 491801937, 448063477, 488539491, 439705403, 400814391, 373040172, 458876871, 319920247, 130558728, 316179694, 334522103, 25711492, 399678229, 434398124, 187800039, 115635965, 142286180, 441372835, 427997810, 320827843, 252702690, 252334734, 491250377, 468408912, 314208502, 358912679, 234549936, 490873343, 42278565, 475402559, 168688623, 442583112, 252260149, 291790253, 344116762, 433258280, 392612040, 222161584, 251204817, 399341726, 476220192, 488858219, 426736104, 356518868 }

  25. {20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 7800, 20000000, 20000000, 20000000, 10000000, 20000000, 20000000, 20000000, 20000000, 10400000, 20000000, 200000, 20000000, 20000000, 13000450, 20000000, 4, 10000000, 20000000, 20000000, 9000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 200000, 20000000, 7800, 20000000, 20000000, 20000000, 20000000, 1000, 20000000, 20000000, 10000000, 20000000, 20000000, 20000000 }

    Returns: {822817017, 822817018, 822817019, 822817020, 822817021, 822817022, 822817023, 822817024, 822817025, 375366, 822817026, 822817027, 822817028, 439416574, 822817029, 822817030, 822817031, 822817032, 455416581, 822817033, 9216578, 822817034, 822817035, 556834135, 822817036, 176, 439416585, 822817037, 822817038, 396416587, 822817039, 822817040, 822817041, 822817042, 822817043, 822817044, 9216593, 822817045, 375394, 822817046, 822817047, 822817048, 822817049, 48998, 822817050, 822817051, 439416601, 822817052, 822817053, 822817054 }

  26. {1, 5, 77089, 9348, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 1, 1, 1, 1, 1, 1 }

    Returns: {1, 176, 3092881, 383241, 780086411, 780086412, 780086413, 780086414, 780086415, 780086416, 780086417, 780086418, 780086419, 780086420, 780086421, 780086422, 780086423, 780086424, 780086425, 780086426, 780086427, 780086428, 780086429, 780086430, 780086431, 780086432, 780086433, 780086434, 780086435, 780086436, 780086437, 780086438, 780086439, 780086440, 780086441, 780086442, 780086443, 780086444, 780086445, 780086446, 780086447, 780086448, 780086449, 44, 45, 46, 47, 48, 49 }

  27. {20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000, 20000000 }

    Returns: {999999951, 999999952, 999999953, 999999954, 999999955, 999999956, 999999957, 999999958, 999999959, 999999960, 999999961, 999999962, 999999963, 999999964, 999999965, 999999966, 999999967, 999999968, 999999969, 999999970, 999999971, 999999972, 999999973, 999999974, 999999975, 999999976, 999999977, 999999978, 999999979, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985, 999999986, 999999987, 999999988, 999999989, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999, 1000000000 }

  28. {19999984, 19999972, 19999910, 19999929, 19999954, 19999962, 19999911, 19999902, 19999937, 19999912, 19999955, 19999974, 19999904, 19999969, 19999974, 19999979, 19999974, 19999972, 19999939, 19999964, 19999999, 19999972, 19999955, 19999912, 19999931, 19194827, 19999944, 19999994, 19999963, 20000000, 19999991, 19999947, 19999932, 19999900, 19999942, 19999987, 19999928, 19999953, 19999989, 19999931, 19999931, 19999909, 19999905, 19999902, 19999978, 19999979, 19999981, 19999917, 19999916, 19999919 }

    Returns: {999192249, 999192121, 999190339, 999191057, 999191765, 999191938, 999190385, 999189983, 999191313, 999190428, 999191790, 999192152, 999190081, 999192071, 999192153, 999192210, 999192155, 999192126, 999191379, 999191985, 999192309, 999192128, 999191800, 999190441, 999191141, 959741326, 999191523, 999192299, 999191969, 999192311, 999192291, 999191606, 999191181, 999189911, 999191474, 999192272, 999191047, 999191758, 999192283, 999191153, 999191154, 999190330, 999190154, 999190017, 999192206, 999192217, 999192234, 999190655, 999190617, 999190730 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: