Data Labeling Task Scheduler

Problem Overview

This OpenAI Machine Learning Engineer question was reported as a two-part coding problem about constructing a schedule for data labeling work.

Part 1: Easy Version

Build any valid schedule for the given tasks. A valid schedule is one where no two tasks from the same group are scheduled at the same time, and each task is scheduled at most once.

Part 2: Hard Version

Maximize the number of tasks scheduled. If it's impossible to schedule all tasks, output any valid partial schedule.

Problem Statement

Given an array of tasks where each task has a unique group and a deadline, construct a schedule that satisfies the following conditions:

1. No two tasks from the same group are scheduled at the same time.
2. Each task is scheduled at most once.

The schedule is represented as a list of non-negative integers, where each integer represents the task's index in the input array.

Input

• tasks: A list of tuples, where each tuple contains (group, deadline).
• N: The number of tasks.

Output

• For Part 1: Return any valid schedule.
• For Part 2: Return a schedule that maximizes the number of tasks scheduled, or any valid partial schedule if it's impossible to schedule all tasks.

Constraints

• 1 <= N <= 100
• 0 <= group < N
• 0 <= deadline <= N

Examples

Example 1

Input: tasks = [(1, 4), (2, 1), (3, 2), (4, 3)], N = 4 Output: [2, 1, 3] or any other valid schedule

Example 2

Input: tasks = [(1, 2), (2, 1), (3, 3), (4, 2)], N = 4 Output: [2, 3] or any other valid schedule that maximizes the number of tasks

Hints

1. Sort the tasks based on their deadlines.
2. Use a greedy approach to schedule tasks with earlier deadlines first.
3. Keep track of the last scheduled time for each group.

Solution

`python def scheduleTasks(tasks, N): # Sort tasks based on deadlines tasks.sort(key=lambda x: x[1])

# Initialize schedule and last scheduled time for each group
schedule = []
last_scheduled = [0] * N

for task in tasks:
    group, deadline = task
    
    # Find the latest possible time to schedule the task
    for i in range(deadline, -1, -1):
        if last_scheduled[group] < i:
            schedule.append(task[0])  # Append task index
            last_scheduled[group] = i + 1
            break

return schedule

Example usage

tasks = [(1, 4), (2, 1), (3, 2), (4, 3)] N = 4 print(scheduleTasks(tasks, N)) # Output: [2, 1, 3] or any other valid schedule `

This solution sorts the tasks based on their deadlines and uses a greedy approach to schedule tasks with earlier deadlines first. It keeps track of the last scheduled time for each group to ensure no two tasks from the same group are scheduled at the same time.