Question

Google | OA | Online Coding Test Questions and Solutions | Set - 32 | 2022

Answer 1

QUESTION:
As Google declared work from home it is important to plan and estimate how much time it will take to complete a set of certain tasks.
There are x tasks assigned to you. While planning you have already estimated these tasks will take a certain amount of time. Let these times be in an array timeRequired of length x where y'th task takes timeRequired[y] hours to finish.
ConcentratedHoursSlot is a number of hours you can work at most at a stretch and then take a break.

 

These are the following conditions to complete the task:

 

1. If you start a task in a given concentrated slot, you must complete the task in the same slot.
2. You can start the next task immediately after completing the previous task
3. You may complete the task in any order

 

Given the timeRequired[] and ConcentratedHoursSlot, return the minimum number of slots required to finish all the tasks adhering to the above conditions.

 

ConcentratedHoursSlot will always be greater or equal to max element in time_required[y].

 

Example1:
Input:
time_required=[2,3,4], concentratedHoursSlot=5
Output: 2
Explanation:
You can finish the first two tasks in one slot.

 

• First Slot: Finish the first two tasks [2+3=5 hours]
• Second slot: Finish the last task in 4 hours

 

Example2:
Sample input
3
1 4 3
4
Sample output
2
Explanation:
You can finish the first and third tasks in one slot.

 

• First Slot: Finish the first and third tasks [1+3=4 hours]
• Second slot: Finish the second task in 4 hours

 

So the minimum number of slots required is 2.

Comments

Approach: Greedy + Sorting + Two Pointer

Sort the time[] array and use 2 pointer.
First Pointer on start, i = 0
Second Pointer on end, j = n - 1;

Now, in every iteration try to pick from both sides & when you can't pick from both sides, increment the answer by 1. Do it until i > j;