Task Prioritization with Limited Time - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the goal of the problem?
  • A: The goal is to determine the maximum number of tasks that can be completed within a given time limit.
• Q: What are the inputs?
  • A: The inputs are a list of task durations (integers) and a time limit (integer).
• Q: What are the outputs?
  • A: The output is an integer representing the maximum number of tasks that can be completed within the given time limit.
• Q: How should tasks be prioritized?
  • A: Tasks with shorter durations should be prioritized first to maximize the number of tasks completed.
• Q: What assumptions can be made about the task durations?
  • A: Task durations are positive integers.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: To maximize the number of tasks within the given time limit, sort the tasks by duration in ascending order. Then, iterate through the sorted tasks, summing the durations until the next task cannot be completed without exceeding the time limit.

1) Sort the `tasks` list in ascending order.
2) Initialize `completed_tasks` to 0 and `current_time` to 0.
3) Iterate through the sorted list of tasks:
   a) Check if adding the current task's duration to `current_time` will exceed `time_limit`.
   b) If it will not exceed the limit, add the task's duration to `current_time` and increment `completed_tasks`.
   c) If it will exceed the limit, stop the iteration.
4) Return `completed_tasks`, which now holds the maximum number of tasks that can be completed within the time limit.

**⚠️ Common Mistakes**

- Forgetting to sort the task durations before trying to maximize the number of tasks.
- Not correctly updating the current time and task count as tasks are added.
- Assuming tasks can only be completed in the order they are given rather than sorting them.

I-mplement

from collections import deque

def max_tasks_within_time(tasks, time_limit):
    task_queue = deque(sorted(tasks))
    completed_tasks = 0
    current_time = 0

    while task_queue and current_time + task_queue[0] <= time_limit:
        current_task = task_queue.popleft()
        current_time += current_task
        completed_tasks += 1

    return completed_tasks

Example Usage:

tasks = [5, 10, 7, 8]
time_limit = 20
print(max_tasks_within_time(tasks, time_limit))  # Output: 3

tasks_2 = [2, 4, 6, 3, 1]
time_limit = 10
print(max_tasks_within_time(tasks_2, time_limit))  # Output: 4

tasks_3 = [8, 5, 3, 2, 7]
time_limit = 15
print(max_tasks_within_time(tasks_3, time_limit))  # Output: 3