0 votes 0 votes Answer given is Option A , but here we wil first sort the jobs in order of profit , for each value of deadline scan linearly in the array depending on the value of deadline , so it should take O(n^2) in worst case . Algorithms gatebook test-series algorithm-design + – radha gogia asked Nov 16, 2018 • retagged Jun 11, 2022 by Arjun radha gogia 512 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Navneet Kalra commented Nov 16, 2018 reply Follow Share Mam ....if you solve it by set the solution will come in theta(n) time... to know how solution is coming theta(n) please search about job scheduling problem and open mit opencourse ware notes there they have mentioned about solution of this problem by taking set... 0 votes 0 votes srestha commented Nov 16, 2018 reply Follow Share Here profit can be changed according to max profit. But deadline should be 1 for each job right? So, say we find max profit in (n-1) time, then it will be O(n) 0 votes 0 votes Navneet Kalra commented Nov 16, 2018 reply Follow Share Yes...but for that we have to follow the approach as i mentioned..by the approach which mam mentioned above it will take theta(n^2) 0 votes 0 votes radha gogia commented Nov 17, 2018 reply Follow Share @srestha , cpu quanta is 1 unit , deadline is tk right ? Becoz it is already mentioned that the job should be started of before tk . 0 votes 0 votes Manas Mishra commented Nov 17, 2018 reply Follow Share @navneet can u provide the link 0 votes 0 votes kumar.dilip commented Nov 17, 2018 reply Follow Share @Manas Mishra https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-204-computer-algorithms-in-systems-engineering-spring-2010/lecture-notes/MIT1_204S10_lec10.pdf 1 votes 1 votes Please log in or register to add a comment.