Job Sequencing Problem ~ Ankur's Blog

techiedelight

	#include<bits/stdc++.h>
	using namespace std;
	#define MAX 2000100

	typedef long long ll;

	struct JOB{
	char id;
	int deadline, profit;
	};

	struct Disjointset
	{
	int *parent;
	Disjointset(int n){
	parent = new int[n+1];

	// Every node is parent of itself
	for(int i = 0; i <= n; i++)parent[i] = i;
	}

	int find(int s){
	if(s == parent[s])return s;
	return parent[s] = find(parent[s]);
	}

	void merge(int u, int v){
	parent[v] = u;
	}
	};

	bool cmp(JOB a, JOB b)
	{
	return (a.profit > b.profit);
	}

	int findMaxDeadline(struct JOB ar[], int n)
	{
	int ans = INT_MIN;
	for(int i = 0; i < n; i++)ans = max(ans, ar[i].deadline);
	return ans;
	}

	int printJobScheduling(JOB ar[], int n)
	{
	sort(ar, ar+n, cmp);

	int MxDead = findMaxDeadline(ar, n);
	Disjointset ds(MxDead);

	for(int i = 0; i < n; i++){

	int availableSlot = ds.find(ar[i].deadline);

	if(availableSlot > 0){
	ds.merge(ds.find(availableSlot-1), availableSlot);
	cout << ar[i].id<< " ";
	}
	}
	cout << endl;
	}
	int main()
	{
	/*#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif*/
	double start_time = clock();

	int n;
	cin >> n;
	JOB ar[n+2];
	for(int i = 0; i < n; i++){
	char id;
	int deadline,profit;
	cin >> id >> deadline >> profit;
	ar[i].id = id;
	ar[i].deadline = deadline;
	ar[i].profit = profit;
	}

	printJobScheduling(ar, n);


	double end_time = clock();
	printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

	return 0;
	}

view raw JobSequence.cpp hosted with ❤ by GitHub

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 1005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;

	struct Job
	{
	int id, deadline,profit;
	};

	int scheduleJobs(vector<Job> const &jobs)
	{
	//cerr<< "enter-------\n";
	int profit = 0;

	vector<int> slot (MAX, -1);

	// consider each job in decreasing order of their profit
	for( const Job &x: jobs){

	for(int i = x.deadline - 1; i >= 0; i--){
	if(i < MAX && slot[i] == -1){
	slot[i] = x.id;
	profit += x.profit;
	break;
	}
	}
	}

	cout << "The Scheduled jobs are:- ";
	for(int i = 0; i < MAX; i++){
	if(slot[i] != -1){
	cout << slot[i] << " ";
	}
	}

	return profit;
	}


	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	vector<Job> jobs =
	{
	{ 1, 9, 15 }, { 2, 2, 2 }, { 3, 5, 18 }, { 4, 7, 1 }, { 5, 4, 25 },
	{ 6, 2, 20 }, { 7, 5, 8 }, { 8, 7, 10 }, { 9, 4, 12 }, { 10, 3, 5 }
	};

	//for(const Job &x: jobs){
	// cerr << x.id <<" "<< x.deadline << " "<<x.profit<<endl;
	//}
	//cerr << "-----------\n";

	sort(jobs.begin(), jobs.end(),
	[](Job &a, Job &b){
	return a.profit > b.profit;
	}
	);

	for(const Job &x: jobs){
	cerr << x.id <<" "<< x.deadline << " "<<x.profit<<endl;
	}
	int ans = scheduleJobs(jobs);
	cout << "\n Total Profit is: "<<ans << endl;

	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

	return 0;
	}

view raw JobScheduiling.cpp hosted with ❤ by GitHub