// Shortest Job First (SJF) - NON-preemptive, with arrival times and a Gantt chart. // At every decision point, pick the arrived, unfinished process with the smallest burst time. // Ties are broken by earlier arrival, then by lower process number. #include #include #include #include #include using namespace std; struct Process { int pid, at, bt; int ct = 0, tat = 0, wt = 0; // completion, turnaround, waiting bool done = false; }; struct Slice { int pid, start, end; }; // pid = 0 means CPU idle int main() { int n; cin >> n; vector p(n); for (int i = 0; i < n; i++) { p[i].pid = i + 1; cin >> p[i].at >> p[i].bt; } vector gantt; int time = 0, finished = 0; while (finished < n) { int pick = -1; for (int i = 0; i < n; i++) { if (p[i].done || p[i].at > time) continue; if (pick == -1 || p[i].bt < p[pick].bt || (p[i].bt == p[pick].bt && p[i].at < p[pick].at)) pick = i; } if (pick == -1) { // nobody has arrived: CPU idles to next arrival int next = INT_MAX; for (auto& q : p) if (!q.done) next = min(next, q.at); gantt.push_back({0, time, next}); time = next; continue; } gantt.push_back({p[pick].pid, time, time + p[pick].bt}); time += p[pick].bt; // runs to completion: non-preemptive p[pick].ct = time; p[pick].tat = p[pick].ct - p[pick].at; p[pick].wt = p[pick].tat - p[pick].bt; p[pick].done = true; finished++; } cout << "Non-preemptive SJF\n\n"; cout << "PID\tAT\tBT\tCT\tTAT\tWT\n"; double sw = 0, st = 0; for (auto& q : p) { cout << "P" << q.pid << "\t" << q.at << "\t" << q.bt << "\t" << q.ct << "\t" << q.tat << "\t" << q.wt << "\n"; sw += q.wt; st += q.tat; } cout << fixed << setprecision(2); cout << "\nAverage waiting time : " << sw / n << "\n"; cout << "Average turnaround time : " << st / n << "\n\nGantt chart:\n"; string top, nums; auto putNum = [&](int v) { nums += to_string(v); }; for (auto& s : gantt) { string label = (s.pid ? "P" + to_string(s.pid) : string("idle")); if (nums.size() < top.size()) nums += string(top.size() - nums.size(), ' '); putNum(s.start); top += "| " + label + " "; } top += "|"; if (nums.size() < top.size() - 1) nums += string(top.size() - 1 - nums.size(), ' '); putNum(gantt.back().end); cout << top << "\n" << nums << "\n"; }