{"id":2873,"date":"2021-10-25T11:47:34","date_gmt":"2021-10-25T06:17:34","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2873"},"modified":"2021-10-25T11:47:35","modified_gmt":"2021-10-25T06:17:35","slug":"job-sequencing-with-deadlines","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/job-sequencing-with-deadlines\/","title":{"rendered":"Job Sequencing With Deadlines"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-greedy-algorithm\">Approach 1: Greedy Algorithm<\/a><\/li><li><a href=\"#dry-run-with-example\">Dry Run with Example<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--implementation\">C++ <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-set\">Efficient Approach: Using Set<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--implementation-of-approach\">C++ <meta charset=\"utf-8\">Implementation of Approach<\/a><\/li><li><a href=\"#java--implementation-of-approach-\">Java <meta charset=\"utf-8\">Implementation of Approach <\/a><\/li><li><a href=\"#python--implementation-of-approach\">Python <meta charset=\"utf-8\">Implementation of Approach<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array of jobs having a specific deadline and associated with a profit, provided the job is completed within the given deadline. The task is to maximize the profit by arranging the jobs in a schedule, such that only one job can be done at a time.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"375\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Input\"  class=\"wp-image-3177 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-1024x375.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-1024x375.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-300x110.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-768x281.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-1536x563.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-2048x751.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-380x139.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-550x202.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-800x293.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2-1160x425.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Input-2.png 2082w\" ><\/figure>\n\n\n\n<p><strong>Output: <\/strong>J4 J3 J1 J2<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"886\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Output\"  class=\"wp-image-3178 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-1024x886.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-1024x886.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-300x259.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-768x664.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-380x329.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-550x476.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-800x692.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1-1160x1003.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/output-1.png 1421w\" ><\/figure>\n\n\n\n<p><strong>Total profit<\/strong> &#8211; 20 + 25 + 35 + 30 = 110<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-1-greedy-algorithm\">Approach 1: Greedy Algorithm<\/h2>\n\n\n\n<p>Since, the task is to get the maximum profit by scheduling the <strong>jobs<\/strong>, the idea is to approach this problem greedily.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Sort the jobs based on decreasing order of profit.<\/li><li>Iterate through the jobs and perform the following:<ul><li>Choose a <strong>Slot i<\/strong> if:<ul><li><strong>Slot i <\/strong>isn\u2019t previously selected.<\/li><li><strong>I &lt; deadline<\/strong><\/li><li><strong>I <\/strong>is maximum<\/li><\/ul><\/li><li>If no such slot exists, ignore the job and continue.<\/li><\/ul><\/li><\/ul>\n\n\n\n<h2 id=\"dry-run-with-example\">Dry Run with Example<\/h2>\n\n\n\n<p>Given Jobs:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"341\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run\"  class=\"wp-image-3179 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-1024x341.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-1024x341.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-300x100.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-768x256.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-1536x512.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-380x127.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-550x183.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-800x267.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-1160x387.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run.png 1656w\" ><\/figure>\n\n\n\n<p>Sort in decreasing order of profits:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"341\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Sort in decreasing order\"  class=\"wp-image-3180 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-1024x341.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-1024x341.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-300x100.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-768x256.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-1536x512.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-380x127.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-550x183.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-800x267.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order-1160x387.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sort-in-decreasing-order.png 1656w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"702\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"sequence of jobs\"  class=\"wp-image-3181 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-1024x702.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-1024x702.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-300x206.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-768x527.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-1536x1053.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-380x261.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-550x377.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-800x549.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job-1160x795.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sequences-of-job.png 1613w\" ><\/figure>\n\n\n\n<h3 id=\"c--implementation\"><span id=\"c-implementation\">C++ <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Job\n{\n   char id;     \n   int dead;  \n   int profit; \n};\nbool comparison(Job a, Job b)\n{\n     return (a.profit > b.profit);\n}\nvoid printJobScheduling(Job arr[], int n)\n{\n    sort(arr, arr+n, comparison);\n  \n    int result[n];\n    bool slot[n];\n    for (int i=0; i&lt;n; i++)\n        slot[i] = false;\n \n    for (int i=0; i&lt;n; i++)\n    {\n       for (int j=min(n, arr[i].dead)-1; j>=0; j--)\n       {\n          if (slot[j]==false)\n          {\n             result[j] = i;  \n             slot[j] = true;\n             break;\n          }\n       }\n    }\n    for (int i=0; i&lt;n; i++)\n       if (slot[i])\n         cout &lt;&lt; arr[result[i]].id &lt;&lt; \" \";\n}<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Job \n{\n    char id;\n    int deadline, profit;\n  \n    public Job() {}\n  \n    public Job(char id, int deadline, int profit)\n    {\n        this.id = id;\n        this.deadline = deadline;\n        this.profit = profit;\n    }\n    void printJobScheduling(ArrayList&lt;Job> arr, int t)\n    {\n        int n = arr.size();\n        Collections.sort(arr,\n                         (a, b) -> b.profit - a.profit);\n  \n        boolean result[] = new boolean[t];\n        char job[] = new char[t];\n        for (int i = 0; i &lt; n; i++) \n        {\n            for (int j\n                 = Math.min(t - 1, arr.get(i).deadline - 1);\n                 j >= 0; j--) {\n                if (result[j] == false) \n                {\n                    result[j] = true;\n                    job[j] = arr.get(i).id;\n                    break;\n                }\n            }\n        }\n        for (char jb : job) \n        {\n            System.out.print(jb + \" \");\n        }\n        System.out.println();\n    }<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def printJobScheduling(arr, t):\n    n = len(arr)\n    for i in range(n):\n        for j in range(n - 1 - i):\n            if arr[j][2] &lt; arr[j + 1][2]:\n                arr[j], arr[j + 1] = arr[j + 1], arr[j]\n  \n    result = [False] * t\n    job = ['-1'] * t\n    for i in range(len(arr)):\n        for j in range(min(t - 1, arr[i][1] - 1), -1, -1):\n            if result[j] is False:\n                result[j] = True\n                job[j] = arr[i][0]\n                break\n  \n    print(job)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^2), where N is the size of the jobs array<br><strong>Space Complexity:<\/strong> O(1), since no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-set\">Efficient Approach: Using Set<\/h2>\n\n\n\n<p>In the previous approach, for each <strong>job<\/strong>, we had to iterate through all other jobs and find a job satisfying the given conditions. But the time complexity is O(N^2) in the worst case. It can be improved further using sets.<\/p>\n\n\n\n<p>The idea is to apply binary search on the set and find the jobs satisfying the given conditions<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Sort the jobs based on decreasing order of profit.<\/li><li>Create two variables, <strong>total_jobs = 0<\/strong>, <strong>maxprofit = 0.<\/strong><\/li><li>Also, find the maximum deadline among all the jobs.<\/li><li>Initialise a <strong>set<\/strong> storing all the jobs in decreasing order.<\/li><li>Iterate through the jobs and perform the following:<ul><li>If the set is empty or the deadline of the current job is less than the last element of the set, ignore the job.<\/li><li>Else, apply binary search and find the nearest <strong>Slot i, <\/strong>such that <strong>i &lt; deadline<\/strong> and add the profit.<\/li><li>Increment total jobs by 1 and remove the <strong>ith<\/strong> element from the set.<\/li><\/ul><\/li><li>Return the maximum profit.<\/li><\/ul>\n\n\n\n<h3 id=\"c--implementation-of-approach\"><span id=\"c-implementation-of-approach\">C++ <meta charset=\"utf-8\">Implementation of Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool compare(vector&lt;int> &amp;job1, vector&lt;int> &amp;job2)\n{\n    return job1[1] > job2[1];\n}\n \nint jobScheduling(vector&lt;vector&lt;int>> &amp;jobs)\n{\n \n    sort(jobs.begin(), jobs.end(), compare);\n \n    int maxProfit = 0;\n    int maxDeadline = 0;\n    for (int i = 0; i &lt; jobs.size(); i++)\n    {\n        maxDeadline = max(maxDeadline, jobs[i][0]);\n    }\n    set&lt;int, greater&lt;int>> slots;\n    for (int i = maxDeadline; i > 0; i--)\n    {\n        slots.insert(i);\n    }\n \n    for (int i = 0; i &lt; jobs.size(); i++)\n    {\n        if (slots.size() == 0 || jobs[i][0] &lt; *slots.rbegin())\n        {\n            continue;\n        }\n \n        int availableSlot = *slots.lower_bound(jobs[i][0]);\n        maxProfit = maxProfit + jobs[i][1];\n        slots.erase(availableSlot);\n   }\n \n    return maxProfit;\n}<\/pre>\n\n\n\n<h3 id=\"java--implementation-of-approach-\"><span id=\"java-implementation-of-approach\">Java <meta charset=\"utf-8\">Implementation of Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int jobScheduling(int[][] jobs)\n    {\n        Arrays.sort(jobs, new Comparator&lt;int[]>(){\n        public int compare(int[] first, int[] second)\n        {\n            if(first[1] &lt; second[1]) return 1;\n            else return -1;\n        }\n        });\n \n        int maxProfit = 0;\n        int maxDeadline = 0;\n        for (int i = 0; i &lt; jobs.length; i++)\n        {\n            maxDeadline = Math.max(maxDeadline, jobs[i][0]);\n        }\n        TreeSet&lt;Integer> set = new TreeSet&lt;Integer>();\n        for (int i = maxDeadline; i > 0; i--)\n        {\n            set.add(i);\n        }\n        TreeSet&lt;Integer> slots = (TreeSet&lt;Integer>)set.descendingSet();\n \n        for (int i = 0; i &lt; jobs.length; i++)\n        {\n            if (slots.size() == 0 || jobs[i][0] &lt; slots.last())\n            {\n                continue;\n            }\n \n            Integer availableSlot = -1;\n \n            for (Integer val : slots)\n        {\n                if (val &lt;= jobs[i][0])\n                {\n                    availableSlot = val;\n                    break;\n                }\n            }\n \n            if (availableSlot != -1)\n            {\n                maxProfit = maxProfit + jobs[i][1];\n \n                slots.remove(availableSlot);\n            }\n        }\n \n        return maxProfit;\n    }<\/pre>\n\n\n\n<h3 id=\"python--implementation-of-approach\"><span id=\"python-implementation-of-approach\">Python <meta charset=\"utf-8\">Implementation of Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import bisect\n \ndef jobScheduling(jobs):\n \n    jobs.sort(key = lambda x: (-x[1], -x[0]))\n    maxProfit = 0\n    maxDeadline = 0\n \n    for i in range(0, len(jobs)):\n        maxDeadline = max(maxDeadline, jobs[i][0])\n \n    slots = list()\n \n \n    for i in range(1, maxDeadline + 1):    \n        slots.append(i)\n \n    maxProfit = 0\n    for i in range(len(jobs)):\n \n        if len(slots) == 0 or jobs[i][0] &lt; slots[0]:\n            continue\n \n        availableSlot = slots[bisect.bisect(slots, jobs[i][0]) - 1]\n        maxProfit += jobs[i][1]\n        slots.remove(availableSlot)\n \n    return maxProfit<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(NlogN), where N is the size of the jobs array<br><strong>Space Complexity:<\/strong> O(max(deadline)), since <strong>set <\/strong>is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p>Q. <strong>Do we need to sort the jobs array?<br><\/strong>Yes, we need to sort the jobs array according to profit. Else, all the possible subsets need to be found, which would lead to an exponential solution.<\/p>\n\n\n\n<p>Q. <strong>What is the most efficient algorithm to solve the Job Sequencing problem?<br><\/strong>The job sequencing problem can be solved using the binary search approach using sets.            The idea is to find the job corresponding to an <strong>ith<\/strong> job whose deadline is less than the current job. This leads to an O(NlogN) approach.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of jobs having a specific deadline and associated with a profit, provided the&hellip;\n","protected":false},"author":4,"featured_media":3176,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[486,472],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2873"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2873"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2873\/revisions"}],"predecessor-version":[{"id":3182,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2873\/revisions\/3182"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3176"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}