← Back to Heap Pattern

📚 Schedule Tasks on Minimum Machines – Java Cheat Sheet

📌 What Is It?

The problem involves scheduling tasks on the minimum number of machines such that no two tasks overlap on the same machine. Each task has a start time and an end time.

To solve this efficiently, we use a min-heap to track the end times of tasks currently assigned to machines:

• Sort the tasks by their start times.
• Use a min-heap to keep track of the earliest end time of tasks currently running on machines.
• If a task can reuse a machine (its start time is greater than or equal to the earliest end time), update the heap.
• Otherwise, allocate a new machine.

🧱 Pattern Template

class Solution {
    public int minMachines(int[][] tasks) {
        // Step 1: Sort tasks by start time
        Arrays.sort(tasks, (a, b) -> a[0] - b[0]);

        // Step 2: Use a min-heap to track end times of tasks
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int[] task : tasks) {
            int start = task[0];
            int end = task[1];

            // Step 3: If the current task can reuse a machine, remove the earliest end time
            if (!minHeap.isEmpty() && minHeap.peek() <= start) {
                minHeap.poll();
            }

            // Step 4: Add the current task's end time to the heap
            minHeap.offer(end);
        }

        // Step 5: The size of the heap is the minimum number of machines required
        return minHeap.size();
    }
}

📊 Time Complexity

• Sorting Tasks: O(n log n) – Sorting the tasks by start time.
• Heap Operations: O(n log n) – Adding and removing elements from the heap for n tasks.
• Overall Complexity: O(n log n).

✅ Use Cases

• Scheduling tasks on limited resources (e.g., machines, rooms)
• Finding the minimum number of resources required for non-overlapping intervals
• Applications in job scheduling, meeting room allocation, etc.

📘 Common LeetCode Problems

• 253. Meeting Rooms II [Medium] Heap
• 1942. The Number of the Smallest Unoccupied Chair [Medium] Min Heap

🧪 Example: Schedule Tasks on Minimum Machines

Input: tasks = [[0, 30], [5, 10], [15, 20]]
Output: 2

Explanation:
- Task 1: [0, 30] requires a machine.
- Task 2: [5, 10] requires a second machine.
- Task 3: [15, 20] can reuse the second machine after Task 2 ends.

💡 Pro Tips

• Sort tasks by start time to process them in chronological order.
• Use a min-heap to efficiently track the earliest end time of tasks.
• Edge cases: overlapping tasks, tasks with the same start and end times, empty input.