Unit 4 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
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.
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