Maximum Tasks with Cooldown and Deadlines - Teradata Online Assessment IIT R

Problem Preview

"You are given a list of tasks. Each task is represented by two integers: `[id, deadline]` where: * `id` is the type/ID of the task. * `deadline` is the latest time by which the task must be completed. Each task takes **1 unit of time** to complete. You are also given an integer `cooldown`. Your goal is to complete the **maximum possible number of tasks** while satisfying all deadlines and the following cooldown rule. ### Cooldown Rule Consider two consecutively completed tasks: * If their IDs are **different**, the next task can be completed immediately. * If their IDs are **the same**, a cooldown of `cooldown` units must be applied before another task with the same ID can be completed. You may choose the order in which tasks are executed, and you are **not required to complete every task**. A task can only be completed if its completion time does not exceed its deadline. Return the **maximum number of tasks** that can be completed. ### Input Format * The first line contains an integer `N`, the number of tasks. * The next `N` lines contain two integers `id` and `deadline`, representing each task. * The last line contains an integer `cooldown`. ### Output Format Print a single integer representing the maximum number of tasks that can be completed. ### Example #### Input ```text 5 1 2 1 5 2 2 2 4 1 7 1 ``` #### Output ```text 4 ``` ### Explanation A valid ordering can be constructed by alternating task IDs whenever possible. For example: ```text Task ID: 1 → 2 → 1 → 2 ``` Since consecutive tasks have different IDs, no cooldown is required between them. The selected tasks can all be completed within their respective deadlines, giving a maximum of `4` completed tasks. ### Constraints * `1 ≤ N ≤ 2 × 10^5` * `1 ≤ id ≤ 10^9` * `1 ≤ deadline ≤ 10^9` * `0 ≤ cooldown ≤ 10^9`"