Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Schedule Tasks on Minimum Machines

Explore how to schedule tasks on machines to minimize the number of machines required. Understand the use of heaps to manage overlapping time intervals and efficiently allocate resources based on start and end times to solve scheduling problems.

We'll cover the following...

Statement

We are given an input array, tasks, where tasks[i] =[starti,endi]= [start_i, end_i] represents the start and end times of nn tasks. Our goal is to schedule these tasks on machines given the following criteria:

  1. A machine can execute only one task at a time.

  2. A machine can begin executing a new task immediately after completing the previous one.

  3. An unlimited number of machines are available.

Find the minimum number of machines required to complete these nn tasks.

Constraints:

  • n==n == tasks.length

  • 1≤1 \leq tasks.length ≤103\leq 10^3

  • 0≤0 \leq tasksi.start << tasksi.end ≤104\leq 10^4

Examples

canvasAnimation-image
1 / 4

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Schedule Tasks on Minimum Machines

1.

What is the minimum number of machines required to schedule the following tasks?

[[1,7],[8,9],[3,6],[9,14],[6,7]][[1, 7], [8, 9], [3, 6], [9, 14], [6, 7]]

A.

3

B.

2

C.

5

D.

1

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5
6

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Solution.java
import java.util.*;
class Solution {
    public static int minimumMachines(int[][] tasks) {
      
        // Replace this placeholder return statement with your code
        return -1;
    }
}
Schedule Tasks on Minimum Machines