#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Định nghĩa cấu trúc cho một công việc
struct Job {
int profit; // Lợi nhuận của công việc
int deadline; // Thời hạn của công việc
};
// Hàm so sánh để sắp xếp các công việc theo thời gian thực hiện tăng dần
bool compare(Job a, Job b) {
return (a.profit < b.profit);
}
// Hàm lập lịch ưu tiên đúng hạn
void scheduleJobs(vector<Job>& jobs, int n) {
// Bước 1: Sắp xếp các công việc theo thời gian thực hiện tăng dần
sort(jobs.begin(), jobs.end(), compare);
// Mảng để lưu kết quả về thời gian bắt đầu, kết thúc và trạng thái của từng công việc
vector<pair<int, pair<int, string>>> schedule;
// Bước 2: Tính thời gian thực tế hoàn thành mỗi công việc
int current_time = 0;
for (int i = 0; i < n; i++) {
int start_time = current_time;
int end_time = start_time + jobs[i].profit;
string status = (end_time <= jobs[i].deadline) ? "Đúng hạn" : "Trễ hạn";
schedule.push_back({jobs[i].profit, {start_time, status}});
current_time = end_time;
}
// Bước 3: In ra kết quả
cout << "Công việc | Thời gian bắt đầu | Thời gian kết thúc (ci) | Thời hạn (di) | Trạng thái" << endl;
cout << "---------------------------------------------------------------------------------------" << endl;
int on_time_count = 0;
int late_count = 0;
for (int i = 0; i < n; i++) {
cout << "(" << jobs[i].profit << "; " << jobs[i].deadline << ")" << "\t\t"
<< schedule[i].second.first << "\t\t" << schedule[i].second.first + schedule[i].first << "\t\t\t"
<< jobs[i].deadline << "\t\t" << schedule[i].second.second << endl;
if (schedule[i].second.second == "Đúng hạn")
on_time_count++;
else
late_count++;
}
// In ra kết quả cuối cùng
cout << "\nKết quả cuối cùng: Có " << on_time_count << " công việc hoàn thành đúng hạn và " << late_count << " công việc hoàn thành trễ hạn." << endl;
}
int main() {
// Nhập số lượng công việc
int n;
cout << "Nhập số lượng công việc: ";
cin >> n;
vector<Job> jobs(n);
cout << "Nhập thông tin cho từng công việc (profit, deadline):\n";
for (int i = 0; i < n; i++) {
cin >> jobs[i].profit >> jobs[i].deadline;
}
scheduleJobs(jobs, n);
return 0;
}