Maximize optional tasks under daily limit

Q: Maximize optional tasks under daily limit

This question evaluates algorithmic problem-solving in scheduling and combinatorial optimization, assessing understanding of capacity-constrained assignment, greedy or matching strategies, and correctness and complexity reasoning.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an integer limit and two integer arrays required and optional of length n. For each day i, you must schedule required[i]. If time remains on that day (not exceeding limit), you may schedule at most one optional task; each optional task can be used at most once and can be assigned to any day. Goal: maximize the number of optional tasks scheduled across n days without exceeding the daily limit. Return: (

the maximum count of scheduled optional tasks, and (
one valid assignment of optional tasks to days (or indicate none for a day). Example: limit = 7 required = [4, 5, 2, 4] optional = [5, 6, 3, 4] One optimal plan schedules 2 optional tasks. Answer the following:

Describe an efficient algorithm, prove why it is correct, and analyze time and space complexity.
Implement the algorithm in the language of your choice.
How would your approach change if each optional task were tied to a specific day (i.e., optional[i] can only be used on day i)?
How would you handle cases where some required[i] > limit?
How would you generalize if up to k optional tasks could be scheduled per day?

Maximize optional tasks under daily limit

Overview

Comments (0)