Job Sequencing Problem

Posted in

Job Sequencing Problem

Maaz Bin Asad
Last updated on June 9, 2022

    Problem

    Given a set of jobs, each with its own deadline and corresponding profit. You get profit only if you complete a job before or on the deadline. Given that each work requires a single unit of time. How can overall profit be maximised if only one task may be performed at a time.

    Sample Input

    { {1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}}

    Sample Output

    Maximum profit sequence of jobs 
    3 1 5

    Approach

    We can follow a greedy approach to solve the given problem. We can sort the jobs on the basis of decreasing order of profits. Then, for each job, we traverse from a given deadline to 0 and check if some slot is free. If a free slot is found, we can mark this slot is occupied. To mark slots as occupied, we can use a set or an array. This approach takes O(NlogN) time and O(N) space.For the above sample input, here the time slots at which we do the jobs.Job 3 ? 1 (got profit of 27)Job 1 ? 2 (got profit of 100)Job 5 ? 3 (got profit of 15)

    C++

    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct Job
    {
    int id; // Job Id
    int deadline; // Deadline of job
    int profit; // Profit of job
    };
    bool comparison(Job a, Job b)
    {
    return (a.profit > b.profit);
    }
    void solve(Job arr[], int n)
    {
    // Sort all jobs according to decreasing order of prfit
    sort(arr, arr+n, comparison);
    int result[n];
    bool slot[n];
    for (int i=0; i<n; i++)
    slot[i] = false;
    for (int i=0; i<n; i++) { for (int j=min(n, arr[i].deadline)-1; j>=0; j--)
    {
    // Free slot found
    if (slot[j]==false)
    {
    result[j] = i;
    slot[j] = true;
    break;
    }
    }
    }
    for (int i=0; i<n; i++)
    if (slot[i])
    cout << arr[result[i]].id << " ";
    }
    int main()
    {
    Job arr[] = { {1, 2, 100}, {2, 1, 19}, {3, 2, 27},
    {4, 1, 25}, {5, 3, 15}};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Maximum profit sequence of jobs \n";
    solve(arr, n);
    return 0;
    }

    Output

    Maximum profit sequence of jobs 
    3 1 5

    Python

    def solve(arr, t):
     n = len(arr)
     for i in range(n):
     for j in range(n - 1 - i):
     if arr[j][2] < arr[j + 1][2]:
     arr[j], arr[j + 1] = arr[j + 1], arr[j]
     result = [False] * t
     ans = ['-1'] * t
     for i in range(len(arr)):
     for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
     if result[j] is False:
     result[j] = True
     ans[j] = arr[i][0]
     break
     print(ans)
    arr = [[1, 2, 100],
     [2, 1, 19],
     [3, 2, 27],
     [4, 1, 25],
     [5, 3, 15]]
    print("Maximum profit sequence of jobs")
    solve(arr, 3)

    Output

    Maximum profit sequence of jobs
    [3, 1, 5]

    C#

    using System;
    using System.Collections.Generic;
    class Solutions : IComparer<Job>
    {
    public int Compare(Job x, Job y)
    {
    if (x.profit == 0 || y.profit== 0)
    {
    return 0;
    }
    return (y.profit).CompareTo(x.profit);
    }
    }
    public class Job{
    public int deadline, profit, id;
    public Job() {}
    public Job(int id, int deadline, int profit)
    {
    this.id = id;
    this.deadline = deadline;
    this.profit = profit;
    }
    void solve(List<Job> arr, int t)
    {
    // Length of array
    int n = arr.Count;
    Solutions solution = new Solutions();
    arr.Sort(solution);
    bool[] result = new bool[t];
    int[] job = new int[t];
    for (int i = 0; i < n; i++)
     {
     for (int j = Math.Min(t - 1, arr[i].deadline - 1); j >= 0; j--)
     {
    if (result[j] == false)
    {
    result[j] = true;
    job[j] = arr[i].id;
    break;
    }
    }
    }
    foreach (int itr in job)
    {
    Console.Write(itr + " ");
    }
    Console.WriteLine();
    }
    static public void Main ()
    {
    List<Job> arr = new List<Job>();
    arr.Add(new Job(1, 2, 100));
    arr.Add(new Job(2, 1, 19));
    arr.Add(new Job(3, 2, 27));
    arr.Add(new Job(4, 1, 25));
    arr.Add(new Job(5, 3, 15));
    Console.WriteLine("Maximum profit sequence of jobs");
    Job job = new Job();
    job.solve(arr, 3);
    }
    }
    

    Output

    Maximum profit sequence of jobs 
    3 1 5

    People are also reading:

    Leave a Comment on this Post

    0 Comments