Task Scheduler

Problem Statement

Write a Java program that simulates a task scheduler using a priority queue. The program should enqueue tasks, each with a description (string) and priority (integer), and dequeue them in order of highest priority, printing each task as it is processed. The priority queue should ensure that tasks with higher priority numbers are dequeued first, and tasks with equal priorities are processed in FIFO order. Test the implementation with various sequences of enqueue and dequeue operations, including edge cases like empty queues and tasks with equal priorities. You can visualize this as a manager prioritizing urgent tasks in a to-do list, ensuring the most critical tasks are handled first.

Input: A sequence of operations, where each operation is either:

• Enqueue: Add a task with a description (string) and priority (integer) to the priority queue (e.g., "Write report", 3).
• Dequeue: Remove and process the task with the highest priority. Output: For each operation, print the action performed (enqueue or dequeue) and, for dequeue, the processed task’s description or a message if the queue is empty. Constraints:
• Queue size is between 0 and 10^5.
• Task descriptions are non-empty strings containing printable ASCII characters, or null (handled gracefully).
• Priorities are integers in the range [-10^9, 10^9].
• The queue may be empty when dequeue is called. Example:
• Input: Operations = [enqueue("Task1", 3), enqueue("Task2", 1), enqueue("Task3", 3), dequeue, dequeue]
• Output:

  Enqueued Task1 (priority 3)
  Enqueued Task2 (priority 1)
  Enqueued Task3 (priority 3)
  Processed task: Task1
  Processed task: Task3
  

• Explanation: Task1 and Task3 (priority 3) are processed before Task2 (priority 1) due to higher priority.
• Input: Operations = [dequeue on empty queue]
• Output: Queue empty, cannot dequeue

Pseudocode

CLASS Task
    SET description to string
    SET priority to integer
ENDCLASS

CLASS PriorityQueue
    SET array to new Task array of size 1000
    SET size to 0
    
    FUNCTION enqueue(description, priority)
        IF size equals array length THEN
            RETURN false (queue full)
        ENDIF
        SET newTask to new Task(description, priority)
        SET array[size] to newTask
        CALL siftUp(size)
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION siftUp(index)
        WHILE index > 0
            SET parent to (index - 1) / 2
            IF array[index].priority <= array[parent].priority THEN
                BREAK
            ENDIF
            SWAP array[index] and array[parent]
            SET index to parent
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null (queue empty)
        ENDIF
        SET result to array[0]
        SET array[0] to array[size - 1]
        DECREMENT size
        IF size > 0 THEN
            CALL siftDown(0)
        ENDIF
        RETURN result
    ENDFUNCTION
    
    FUNCTION siftDown(index)
        SET maxIndex to index
        WHILE true
            SET left to 2 * index + 1
            SET right to 2 * index + 2
            IF left < size AND array[left].priority > array[maxIndex].priority THEN
                SET maxIndex to left
            ENDIF
            IF right < size AND array[right].priority > array[maxIndex].priority THEN
                SET maxIndex to right
            ENDIF
            IF maxIndex equals index THEN
                BREAK
            ENDIF
            SWAP array[index] and array[maxIndex]
            SET index to maxIndex
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
ENDCLASS

FUNCTION simulateTaskScheduler(operations)
    CREATE queue as new PriorityQueue
    FOR each operation in operations
        IF operation.type equals "enqueue" THEN
            CALL queue.enqueue(operation.description, operation.priority)
            PRINT enqueued task and priority
        ELSE IF operation.type equals "dequeue" THEN
            SET task to queue.dequeue()
            IF task is null THEN
                PRINT queue empty message
            ELSE
                PRINT processed task description
            ENDIF
        ENDIF
    ENFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL simulateTaskScheduler(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Task class to store task description (string) and priority (integer).
2. Define a PriorityQueue class using a max-heap with: a. An array to store tasks, with size to track elements. b. enqueue: Add task to end, sift up to maintain heap property. c. dequeue: Remove root (highest priority), move last task to root, sift down. d. siftUp: Move task up if its priority is higher than parent’s. e. siftDown: Move task down to maintain max-heap property. f. isEmpty: Check if queue is empty.
3. In simulateTaskScheduler: a. Create a PriorityQueue. b. For each operation:
   • If "enqueue", add task with priority, print action.
   • If "dequeue", remove highest-priority task, print task or "Queue empty".
4. In main, test with sequences of enqueue and dequeue operations, including empty queues, single tasks, and equal priorities.

Java Implementation

import java.util.*;

public class TaskScheduler {
    // Task class to store description and priority
    static class Task {
        String description;
        int priority;

        Task(String description, int priority) {
            this.description = description;
            this.priority = priority;
        }
    }

    // Custom priority queue implementation (max-heap)
    static class PriorityQueue {
        private Task[] array;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public PriorityQueue() {
            array = new Task[DEFAULT_SIZE];
            size = 0;
        }

        public boolean enqueue(String description, int priority) {
            if (size == array.length) {
                return false; // Queue full
            }
            Task newTask = new Task(description, priority);
            array[size] = newTask;
            siftUp(size);
            size++;
            return true;
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (array[index].priority <= array[parent].priority) {
                    break;
                }
                // Swap
                Task temp = array[index];
                array[index] = array[parent];
                array[parent] = temp;
                index = parent;
            }
        }

        public Task dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            Task result = array[0];
            array[0] = array[size - 1];
            size--;
            if (size > 0) {
                siftDown(0);
            }
            return result;
        }

        private void siftDown(int index) {
            int maxIndex = index;
            while (true) {
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                if (left < size && array[left].priority > array[maxIndex].priority) {
                    maxIndex = left;
                }
                if (right < size && array[right].priority > array[maxIndex].priority) {
                    maxIndex = right;
                }
                if (maxIndex == index) {
                    break;
                }
                // Swap
                Task temp = array[index];
                array[index] = array[maxIndex];
                array[maxIndex] = temp;
                index = maxIndex;
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        String description;
        Integer priority;

        Operation(String type, String description, Integer priority) {
            this.type = type;
            this.description = description;
            this.priority = priority;
        }
    }

    // Simulates task scheduler
    public void simulateTaskScheduler(List<Operation> operations) {
        PriorityQueue queue = new PriorityQueue();
        for (Operation op : operations) {
            if (op.type.equals("enqueue")) {
                boolean success = queue.enqueue(op.description, op.priority);
                if (success) {
                    System.out.println("Enqueued " + (op.description != null ? op.description : "null") + 
                                      " (priority " + op.priority + ")");
                } else {
                    System.out.println("Enqueue " + (op.description != null ? op.description : "null") + 
                                      " failed: Queue full");
                }
            } else if (op.type.equals("dequeue")) {
                Task task = queue.dequeue();
                if (task == null) {
                    System.out.println("Queue empty, cannot dequeue");
                } else {
                    System.out.println("Processed task: " + task.description);
                }
            }
        }
    }

    // Main method to test task scheduler
    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("enqueue", "Write report", 3),
            new Operation("enqueue", "Send email", 1),
            new Operation("enqueue", "Attend meeting", 3),
            new Operation("dequeue", null, null),
            new Operation("dequeue", null, null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty queue
        List<Operation> case2 = Arrays.asList(
            new Operation("dequeue", null, null)
        );
        testCases.add(case2);
        
        // Test case 3: Single task
        List<Operation> case3 = Arrays.asList(
            new Operation("enqueue", "Debug code", 5),
            new Operation("dequeue", null, null)
        );
        testCases.add(case3);
        
        // Test case 4: Equal priorities
        List<Operation> case4 = Arrays.asList(
            new Operation("enqueue", "Task A", 2),
            new Operation("enqueue", "Task B", 2),
            new Operation("enqueue", "Task C", 2),
            new Operation("dequeue", null, null),
            new Operation("dequeue", null, null)
        );
        testCases.add(case4);
        
        // Test case 5: Null task description
        List<Operation> case5 = Arrays.asList(
            new Operation("enqueue", null, 4),
            new Operation("dequeue", null, null)
        );
        testCases.add(case5);

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            scheduler.simulateTaskScheduler(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Enqueued Write report (priority 3)
Enqueued Send email (priority 1)
Enqueued Attend meeting (priority 3)
Processed task: Write report
Processed task: Attend meeting

Test case 2:
Queue empty, cannot dequeue

Test case 3:
Enqueued Debug code (priority 5)
Processed task: Debug code

Test case 4:
Enqueued Task A (priority 2)
Enqueued Task B (priority 2)
Enqueued Task C (priority 2)
Processed task: Task A
Processed task: Task B

Test case 5:
Enqueued null (priority 4)
Processed task: null

Explanation:

• Test case 1: Enqueues tasks with priorities 3, 1, 3; dequeues highest-priority tasks (Write report, Attend meeting) before Send email.
• Test case 2: Dequeue on empty queue returns error.
• Test case 3: Enqueues and dequeues a single task.
• Test case 4: Enqueues three tasks with equal priority (2), processes in FIFO order (Task A, Task B).
• Test case 5: Enqueues and dequeues a task with null description.

How It Works

• Task: Stores a task’s description and priority.
• PriorityQueue:
  • Uses a max-heap array to store tasks, ensuring highest-priority task is at root.
  • enqueue: Adds task to end, sifts up to maintain heap property.
  • dequeue: Removes root, moves last task to root, sifts down.
  • Equal priorities maintain FIFO order due to heap insertion order.
• simulateTaskScheduler:
  • Enqueues tasks, printing action and priority.
  • Dequeues highest-priority task, printing description or "Queue empty".
• Example Trace (Test case 1):
  • Enqueue "Write report" (3): array=[(Write report,3)], size=1.
  • Enqueue "Send email" (1): array=[(Write report,3),(Send email,1)], size=2.
  • Enqueue "Attend meeting" (3): array=[(Attend meeting,3),(Send email,1),(Write report,3)], size=3 (after sift-up).
  • Dequeue: Returns "Attend meeting", array=[(Write report,3),(Send email,1)], size=2 (after sift-down).
  • Dequeue: Returns "Write report", array=[(Send email,1)], size=1.
• Main Method: Tests normal sequences, empty queue, single task, equal priorities, and null description.

Complexity Analysis Table

Note:

• n is the number of operations.
• Time complexity: O(log n) for enqueue/dequeue due to heap operations; O(n log n) for n operations.
• Space complexity: O(n) for storing up to n tasks.
• Worst case: O(n log n) time for n enqueue/dequeue operations, O(n) space.

✅ Tip: Use a max-heap for a priority queue to ensure highest-priority tasks are processed first. Test with equal priorities to verify FIFO behavior for same-priority tasks.

⚠ Warning: Handle null descriptions and empty queue cases to avoid errors. Ensure the heap maintains its property after each enqueue and dequeue operation.