#include <iostream>
#include <vector>
#include <limits>  // For std::numeric_limits
#include <iomanip> // For std::setw
#include <map>

using namespace std;

struct Process {
    int id;
    int arrival_time;
    int burst_time;
    int completion_time;
    int turnaround_time;
    int waiting_time;
    int response_time;
    int remaining_burst_time;
};

void shortest_job_first(vector<Process>& processes) {
    int n = processes.size();
    int current_time = 0;
    int completed = 0;

    while (completed < n) {
        int min_burst_time = numeric_limits<int>::max();
        int idx = -1;

        for (int i = 0; i < n; ++i) {
            if (processes[i].arrival_time <= current_time &&
                processes[i].remaining_burst_time > 0 &&
                processes[i].remaining_burst_time < min_burst_time) {
                min_burst_time = processes[i].remaining_burst_time;
                idx = i;
            }
        }

        if (idx != -1) {
            if (processes[idx].remaining_burst_time == processes[idx].burst_time) {
                // Response Time
                processes[idx].response_time = current_time - processes[idx].arrival_time;
            }

            current_time += processes[idx].remaining_burst_time;
            processes[idx].completion_time = current_time;
            processes[idx].turnaround_time = processes[idx].completion_time - processes[idx].arrival_time;
            processes[idx].waiting_time = processes[idx].turnaround_time - processes[idx].burst_time;
            processes[idx].remaining_burst_time = 0;
            ++completed;
        } else {
            ++current_time;  // If no process is ready, just increment time
        }
    }
}

void print_results(const vector<Process>& processes) {
    cout << "\nProcess ID\tArrival Time\tBurst Time\tCompletion Time\tTurnaround Time\tWaiting Time\tResponse Time" << endl;
    for (const auto& p : processes) {
        cout << p.id << "\t\t"
             << p.arrival_time << "\t\t"
             << p.burst_time << "\t\t"
             << p.completion_time << "\t\t"
             << p.turnaround_time << "\t\t"
             << p.waiting_time << "\t\t"
             << p.response_time << endl;
    }
}

void print_gantt_chart(const vector<Process>& processes) {
    map<int, int> time_to_process;  // Maps time unit to process ID

    for (const auto& p : processes) {
        for (int t = p.arrival_time; t < p.completion_time; ++t) {
            time_to_process[t] = p.id;
        }
    }

    cout << "\nGantt Chart:" << endl;

    int prev_time = 0;
    for (const auto& entry : time_to_process) {
        int t = entry.first;
        cout << setw(3) << t;
        prev_time = t;
    }
    cout << setw(3) << prev_time + 1 << endl;

    prev_time = 0;
    for (const auto& entry : time_to_process) {
        int t = entry.first;
        if (t > prev_time) {
            for (int i = prev_time; i < t; ++i) {
                cout << "   ";
            }
            cout << "P" << entry.second;
            prev_time = t;
        }
    }
    for (int i = prev_time; i <= (prev_time + 1); ++i) {
        cout << "   ";
    }
    cout << endl;
}

int main() {
    vector<Process> processes(5);

    cout << "Enter arrival and burst times for 5 processes:" << endl;
    for (int i = 0; i < 5; ++i) {
        processes[i].id = i + 1;
        cout << "Arrival time for Process " << processes[i].id << ": ";
        cin >> processes[i].arrival_time;
        cout << "Burst time for Process " << processes[i].id << ": ";
        cin >> processes[i].burst_time;
        processes[i].remaining_burst_time = processes[i].burst_time;
    }

    shortest_job_first(processes);
    print_results(processes);
    print_gantt_chart(processes);

    return 0;
}