Task Scheduler System

Problems to Solve

You will work with a comprehensive task scheduling dataset containing 100 system tasks. Download the CSV file containing task data for analysis:

Dataset Schema

// Example: Task representation for scheduling
class Task {
    String taskId;       // Unique identifier
    int priority;        // 1-5 (use for heap ordering)
    int duration;        // Duration in minutes
    LocalDateTime deadline;    // Must complete by
    List<String> dependencies; // Tasks that must finish first
    String resource;     // Required server/resource
}

// This becomes input for:
// - Priority Queue Scheduling (max-heap by priority)
// - Earliest Deadline First (min-heap by deadline)
// - Topological Sort (dependency graph)
// - Interval Scheduling (resource allocation)

Sample Data Preview

Here is what the data looks like from task_scheduler.csv:

Your project must include all of the following components. Structure your code with clear organization, documentation, and comprehensive testing.

Implement the following algorithms with optimal time and space complexity. Each algorithm should be thoroughly tested and documented.

// Example:
// tasks = [(T1, p=3), (T2, p=5), (T3, p=1)]
// Output: T2 -> T1 -> T3

public List<Task> scheduleByPriority(List<Task> tasks) {
    PriorityQueue<Task> maxHeap = 
        new PriorityQueue<>((a, b) -> b.priority - a.priority);
    
    maxHeap.addAll(tasks);
    List<Task> schedule = new ArrayList<>();
    
    while (!maxHeap.isEmpty()) {
        schedule.add(maxHeap.poll());
    }
    return schedule;
}

// Example:
// T1 -> T2 -> T3 (T2 depends on T1)
// Output: [T1, T2, T3]

public List<Task> topologicalSort(List<Task> tasks) {
    Map<String, Integer> inDegree = new HashMap<>();
    Queue<Task> queue = new LinkedList<>();
    
    // Initialize in-degrees
    for (Task t : tasks) {
        inDegree.put(t.id, t.dependencies.size());
        if (t.dependencies.isEmpty()) {
            queue.offer(t);
        }
    }
    // BFS processing...
}

// Schedule tasks to minimize missed deadlines

public List<Task> scheduleByDeadline(List<Task> tasks) {
    PriorityQueue<Task> minHeap = 
        new PriorityQueue<>(
            Comparator.comparing(t -> t.deadline));
    
    minHeap.addAll(tasks);
    List<Task> schedule = new ArrayList<>();
    
    while (!minHeap.isEmpty()) {
        schedule.add(minHeap.poll());
    }
    return schedule;
}

// Given tasks and cooldown n, find minimum time
// tasks = ["A","A","A","B","B","B"], n = 2
// Output: 8 (A -> B -> idle -> A -> B -> idle -> A -> B)

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char c : tasks) freq[c - 'A']++;
    
    Arrays.sort(freq);
    int maxFreq = freq[25];
    int idleSlots = (maxFreq - 1) * n;
    
    for (int i = 24; i >= 0; i--) {
        idleSlots -= Math.min(freq[i], maxFreq - 1);
    }
    return tasks.length + Math.max(0, idleSlots);
}

// Return true if circular dependency exists

public boolean hasCycle(List<Task> tasks) {
    Map<String, Integer> state = new HashMap<>();
    // 0 = unvisited, 1 = visiting, 2 = visited
    
    for (Task t : tasks) {
        if (dfs(t, state, taskMap)) {
            return true; // Cycle found
        }
    }
    return false;
}

private boolean dfs(Task t, Map<String, Integer> state) {
    if (state.get(t.id) == 1) return true; // Back edge
    if (state.get(t.id) == 2) return false;
    state.put(t.id, 1);
    // ... check dependencies
}

// Maximize number of tasks completed on time

public int maxTasksOnTime(List<Task> tasks) {
    // Sort by deadline
    Collections.sort(tasks, 
        Comparator.comparing(t -> t.deadline));
    
    PriorityQueue<Task> scheduled = 
        new PriorityQueue<>((a,b) -> b.duration - a.duration);
    int currentTime = 0;
    
    for (Task t : tasks) {
        scheduled.offer(t);
        currentTime += t.duration;
        if (currentTime > t.deadline) {
            currentTime -= scheduled.poll().duration;
        }
    }
    return scheduled.size();
}

Implement the following data structures to support efficient scheduling operations. Focus on optimal time complexity for the core operations.

Submit your project via GitHub. Ensure your repository is public and follows the structure below.

task-scheduler-system/
├── src/
│   ├── main/java/
│   │   ├── models/
│   │   │   └── Task.java
│   │   ├── datastructures/
│   │   │   ├── TaskPriorityQueue.java
│   │   │   ├── DependencyGraph.java
│   │   │   ├── TaskRegistry.java
│   │   │   └── ResourceManager.java
│   │   ├── algorithms/
│   │   │   ├── PriorityScheduler.java
│   │   │   ├── TopologicalScheduler.java
│   │   │   ├── DeadlineScheduler.java
│   │   │   ├── TaskSchedulerWithCooldown.java
│   │   │   └── CycleDetector.java
│   │   └── Main.java
│   └── test/java/
│       ├── datastructures/
│       └── algorithms/
├── data/
│   └── task_scheduler.csv
├── docs/
│   ├── algorithm-analysis.md
│   └── complexity-report.md
├── README.md
└── pom.xml (or build.gradle)

Your project will be evaluated on the following criteria. Maximum score is 500 points.