Problem

The Programmers team is currently performing feature improvement tasks. Each feature can only be released when its progress reaches 100%. However, since the development speed of each feature varies, it is possible for features developed later to be completed earlier. In such cases, a feature that is developed later will be released together with the feature in front of it that is scheduled for earlier release.

Given an integer array progresses which represents the current progress of each task and an integer array speeds which represents the daily development speed of each task, implement a function solution that returns an array indicating how many features are released together on each release day.

Constraints

• The number of tasks (length of progresses and speeds) is no more than 100.
• Task progress is a natural number less than 100.
• Task speed is a natural number up to 100.
• Deployment can only happen once per day and occurs at the end of the day. For example, if a task is 95% complete and progresses at a rate of 4% per day, it will be deployable in 2 days.

Example

Explanation of Examples

• Example #1:

  • The first feature is 93% complete and progresses at 1% per day, thus it takes 7 days to complete.
  • The second feature is 30% complete and progresses at 30% per day, thus it takes 3 days. However, it must wait for the first feature to be deployed, hence it is deployed on the 7th day along with the first feature.
  • The third feature is 55% complete and progresses at 5% per day, thus it takes 9 days.
  • As a result, on the 7th day, 2 features are deployed and on the 9th day, 1 feature is deployed.

• Example #2:

  • All features progress at 1% per day. The remaining days for the tasks to be completed are 5 days, 10 days, 1 day, 1 day, 20 days, and 1 day, respectively.
  • Even if a feature is completed, it cannot be deployed until all the preceding features are also ready for deployment.
  • Therefore, 1 feature is deployed on the 5th day, 3 features on the 10th day, and 2 features on the 20th day.

How to Approach?

Step1: Initialize variables in loop

Step2: Array copy and sort

Step3: Designate elements to output array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.*;

public class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Deque<Integer> leftDays = new LinkedList<>();
        Deque<Integer> queue = new LinkedList<>();
        
        for(int i = 0; i < progresses.length; i++){
            int leftDay = (int) (Math.ceil( (100.0 - progresses[i]) / speeds[i]));
            leftDays.offer(leftDay);
        }
        
        while(leftDays.size() != 0){
            int features = leftDays.poll();
            int count = 1;
            while(leftDays.size() != 0 && features >= leftDays.peek()){
                leftDays.poll();
                count++;
            }
            queue.offer(count);
        }
        
        int[] answer = new int[queue.size()];
        
        for(int i = 0; i<answer.length; i++){
            answer[i] = queue.poll();
        }
        return answer;
    }
}