CODEWITHSUNDEEP
algorithmjob-schedulinggreedy
Ak01
Ak01

Reputation: 390

How to find the minimum number of processors to finish n jobs

I originally saw this problem on my university test (unfortunately, I don't have access to this question and the test cases anymore so this is described from memory). The problem is, you are given n jobs with start and finish times, and u have to find the minimum number of processors that can finish ALL jobs. A processor can only do disjoint jobs (jobs that don't overlap).

Sample test case: There are 5 jobs (with start and end time given respectively):

1 11
2 3
3 6
4 6
10 13

The answer is you need a min of 3 processors to complete all the jobs.

processor 1: 1-11
processor 2: 2-3 4-6 10-13
processor 3: 3-6

My idea for this was to use a set of pairs with finish time as first and start time as second of the pair. This way, the jobs would be sorted by finish times. I would then keep iterating over the set and remove all processes that are disjoint for that iteration (using the greedy algorithm of finding the max. no. of jobs a single processor can schedule) and then my answer would be the number of iterations it took until the set was empty.

However, this didn't work on all the test cases. I believe it might be because the algorithm is too slow as inserting and deleting in the set take log n time (which I do for n elements). Then I am also iterating over the set again and again until it is empty.

My question is, is there a better way to do this?

Code:

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
    
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        set<pair<int, int>> a;
        for(int i=0; i < n; ++i)
        {
            int s, f;
            cin >> s >> f;
            a.insert({f, s});
        }
        int cnt = 0;
        while(!a.empty())
        {
            auto range = pair<int, int>(*a.begin());
            a.erase(a.begin());
            for(auto t = a.begin(); t!= a.end(); ++t)
            {
                if(t->second > range.first)
                {
                    range.first = t->second;
                    a.erase(t);
                }
            }
            cnt++;
        }
        cout << cnt << endl;
    }
}

first line of input is number of test cases.

second line of input is number of jobs n.

the next n lines denotes each job with first number being start time and second number being end time

Upvotes: 0

Views: 22123

Answers (1)

Vivek
Vivek

Reputation: 143

It can be done faster, in O(n) time, if the constraints on start and finish time is low. We can make a dp array, in which for each job, we will do dp[job[i].start]+=1 and dp[job[i].end+1]-=1. After calcualting prefix array from it, maximum number will be our answer. This question is very much similar to the minimum number of lecture halls. For more details, you can refer https://www.geeksforgeeks.org/minimum-halls-required-for-class-scheduling/.

Upvotes: 2

Related Questions