ShortestJobFirstPreemptive.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Job {
public:
	string name;
	int start;
	int end;
	int lenght(){return this->end - this->start;};
};

bool cmpStart(Job a, Job b){return a.start < b.start;}
bool cmpEnd(Job a, Job b){return a.end < b.end;}

int main (){		
	vector<Job> jobs;
	Job accepted[20];
	
	Job a = {.name = "President", .start = 0, .end = 10};
	jobs.push_back(a);
	Job b = {.name = "Discrete", .start = 2, .end = 7};
	jobs.push_back(b);
	Job c = {.name = "Tarjan", .start = 4, .end = 14};
	jobs.push_back(c);
	Job d = {.name = "Halting", .start = 9, .end = 16};
	jobs.push_back(d);
	Job e = {.name = "Steiner", .start = 11, .end = 18};
	jobs.push_back(e);
	Job f = {.name = "Volume", .start = 17, .end = 28};
	jobs.push_back(f);
	Job g = {.name = "Programming", .start = 19, .end = 27};
	jobs.push_back(g);
	Job h = {.name = "Process", .start = 25, .end = 33};
	jobs.push_back(h);
	Job i = {.name = "Calculated", .start = 28, .end = 34};
	jobs.push_back(i);
	

	//ALGORITHM NO 1:
	//Sort by begin date
	sort(jobs.begin(), jobs.end(), &cmpStart);
	int j = 0;
	//And accept the first
	accepted[0] = jobs[0];
	//For each element i of jobs and j of accepted
	for (auto i : jobs){
		//If i begins before j's end and it's shorter	
		if (i.start <= accepted[j].end && i.lenght() < accepted[j].lenght())
			accepted[j] = i;
		//If instead i starts after the ending of j (that's why we've sorted the array before)
		if (i.start > accepted[j].end)
			accepted[++j] = i;
	}	
	
	vector<Job> accept;

	//ALGORITHM NO 2:
	//While it isn't empty
	Job fooJob = { .name = "FOO", .start = 123123123, .end = 123917283};
	
	//Loop through the elements
	for(auto i : jobs)
		//Compare i with each j
		for(auto j : jobs){
			//If i ends before j
			if (i.end < j.end){
				//Choose i
				accept.push_back(i);
				//And if j starts before i ends
				if(j.start < i.end)
					j = fooJob;
				i = fooJob;
			}	
		}
		
	for (vector<Job>::iterator iter = accept.begin(); iter != accept.end(); ++iter)
		cout << iter->name << endl;

}