The processes run by non-preemptive shortest job first. Whenever the CPU is free, it picks, among the processes that have arrived and not run yet, the one with the shortest burst. A tie goes to the one that arrived first, and then to the one listed first. A process runs to the end of its burst. If no process is waiting, the CPU idles until the next one arrives.
Input
The first line has n (1 ≤ n ≤ 20). Each of the next n lines has the arrival time and burst time of P1, P2, ... (0 ≤ arrival ≤ 100, 1 ≤ burst ≤ 50), in any order of arrival.
Output
The first line is order: followed by the processes in the order they run, such as order: P1 P4 P2 P3. The second line is average waiting W, with 2 decimal places.
Examples
4 0 5 1 3 2 8 3 2
order: P1 P4 P2 P3 average waiting 4.00
4 2 4 0 3 10 1 3 1
order: P2 P4 P1 P3 average waiting 0.50
Hints
Hint 1
Each time the CPU is free, look at the processes that have arrived and are not done.
Hint 2
Pick the shortest burst; on a tie the earlier arrival; on a tie again, the one listed first.
Hint 3
If none has arrived, move the clock to the earliest arrival among those left.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, arrival[20], burst[20], done[20] = {0};
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &arrival[i], &burst[i]);
int time = 0, total_wait = 0;
printf("order:");
for (int finished = 0; finished < n; finished++) {
int pick = -1;
for (int i = 0; i < n; i++) {
if (done[i] || arrival[i] > time) continue;
if (pick < 0 || burst[i] < burst[pick] || (burst[i] == burst[pick] && arrival[i] < arrival[pick]))
pick = i;
}
if (pick < 0) { /* nobody has arrived: jump to the next arrival */
int next = -1;
for (int i = 0; i < n; i++)
if (!done[i] && (next < 0 || arrival[i] < next)) next = arrival[i];
time = next;
finished--;
continue;
}
total_wait += time - arrival[pick];
time += burst[pick];
done[pick] = 1;
printf(" P%d", pick + 1);
}
printf("\naverage waiting %.2f\n", (double)total_wait / n);
return 0;
}