🙏

জয়  শ্রী  রাম

🕉

---

Prerequisites:

• Topological Sort
• Course Scheduling

Job Scheduling Problems are a very common category of problems often seen in both coding interviews as well as in academia (assignments, tests).
Job Scheduling Problems can be broadly categorized in three types:

1. Sequential Jobs Scheduling with precedence
2. Parallel Jobs Scheduling with Precedence
3. Parallel Jobs Scheduling with Precedence and Relative Deadlines

Most of the job scheduling problems can be solved by any of these approaches:

1. Topological Sort
2. Longest Paths Algorithm
3. Bellman-Ford Algorithm & Negative Cycle Detection

So understanding the concepts of the above three algorithms are very crucial to understand the heart of the Jobs Scheduling Problems. If you understand these algorithms really well, solution to the Jobs Scheduling Problems will occur to you naturally and the problems would look really easy.

We will discuss the Sequential Jobs Scheduling Problem with Precedence here.
So this kind of problems state is that there are certain jobs need to be done but there are some constraints that need to be fulfilled while getting those jobs done. The constraint is that there are certain jobs that are dependent on the completion on some other jobs, and cannot be started until those jobs are completed. This is what we refer to as Precedence. One more constraint for this kind of problems is that you can do only one job at a time. This is why it is sequential. Even if two or more jobs are eligible to be done at the same time, you cannot do them parallelly.
So what we need to do here is processing a job only after getting the jobs on which the job is dependent on first, and this must be true for all the given jobs. This is nothing but the concept of Topological Order or Topological Sorting.

One more thing to notice, each job may have its own duration to complete, but since it is a sequential job scheduling, the durations won't add any extra complexity. In fact, if we just have to do a feasibility test (i.e, determining if a given set of jobs are possible to be completed maintaining all the given constraints/precedence) we won't even have to consider the durations. In fact, the Topological Sorting does not even need any job durations. We would only need the durations if we have to determine how long it takes to process all the jobs from beginning till the end.

Now let's take a look at a real-world problem of this kind:

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solution:

We can represent the input prerequisites as a graph. Let's represent the graph by a list of edges.

Java code:


Login to Access Content




Python code:


Login to Access Content

Related Must-Read Topics:

1. Course Scheduling
2. Dijkstra's Algorithm
3. Longest Paths Algorithm
4. Topological Sort w/ Vertex Relaxation
5. Bellman-Ford Algorithm & Negative Cycle Detection
6. Optimized Bellman-Ford
7. Parallel Job Scheduling
8. Parallel Job Scheduling
   w/ Relative Deadlines
9. Arbitrage

Instructor: