Register

algorithm

• retagged by
1,572 views
1 1 vote
worst case time complexity of job sequencing with deadline using greedy algorithm

1 Answer

3 3 votes
Job Sequencing with Deadline will occur in following  steps:

Step 1: Create an array whose size is equal is to the maximum deadline given.This will take constant time.

Step 2: Sort out the jobs in descending order of their profits. Best complexity: O(nlogn)

Step 3: Take the job one by one(O(n)) and find the particular slots to fix that job based on greedy analysis, worst case, slot will found in O(n) time. total complexity: O(n^2)

so overall complexity: O(1) + O(nlogn) +O(n^2) = O(n^2)...
Voting & Accepting an answer helps improve the community
← Previous · #testbook test serie...Next → · #ADDRESS INSTRUCTION
← Previous in category · algorithmNext in category → · algorithm
Position:
Show:

Related questions

0 0 votes
1 1 answer
536
536 views
Sajal Mallick asked Nov 27, 2023
536 views
Algorithm Madeeasy Workbook
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n logn)...
1 1 vote
1 1 answer
168
168 views
GO Classes asked Aug 29
168 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...
1 1 vote
3 3 answers
12.3k
12.3k views
Deeptimittal97 asked Jul 6, 2017
12,335 views
Optimal Merge Pattern
What will be the time complexity to obtain optimal merge pattern to merge files using greedy technique?
1 1 vote
1 1 answer
433
433 views
NIL DAS asked Dec 10, 2025
433 views
ZEAL TEST ALGORITHM