Task scheduling problem

A job scheduler is a computer application for controlling unattended background program execution. Write a program to implement task scheduling problem which will schedule the tasks?

source Code

package com.dsacode.Algorithm.greedy;
 
import java.util.Arrays;
 
class Job implements Comparable < Job > {
    public char id;
    public Integer dead;
    public int profit;
 
    public Job(char a, int i, Integer k) {
        id = a;
        dead = i;
        profit = k;
    }
 
    public int compareTo(Job o) {
        return this.dead.compareTo(o.dead);
    }
};
 
public class TaskSheduling {
 
    static void printJobScheduling(Job arr[], int n) {
        Arrays.sort(arr);
 
        int[] result = new int[n];
        boolean[] slot = new boolean[n];
 
        for (int i = 0; i < n; i++)
            slot[i] = false;
 
        for (int i = 0; i < n; i++) {
            for (int j = Math.min(n, arr[i].dead) - 1; j >= 0; j--) {
                if (slot[j] == false) {
                    result[j] = i;
                    slot[j] = true;
                    break;
                }
            }
        }
 
        for (int i = 0; i < n; i++)
            if (slot[i])
                System.out.print(arr[result[i]].id +" ");
    }
 
    public static void main(String[] args) {
        Job[] arr = new Job[] { new Job('a', 4, 100), new Job('c', 2, 27),
                new Job('d', 1, 25), new Job('e', 3, 75) };
         
        System.out.print("Task scheduling  sequence of jobs : ");
        printJobScheduling(arr, arr.length);
 
    }
 
}

Task scheduling sequence of jobs : d c e a

Algorithm Explanation

	Sort the jobs based on deadline.
	Initialize the result sequence as the first job in sorted jobs.
	If the current job can fit in the current result sequence without missing the deadline, add the current job to the result.
	Else ignore the current job and print the job sequence.

Time Complexity

Reference

1. http://cc.ee.ntu.edu.tw/~ywchang/Courses/Alg/unit5p.pdf
2. https://en.wikipedia.org/wiki/Interval_scheduling
3. https://en.wikipedia.org/wiki/Scheduling_%28computing%29