Immigration Problem(with.Java)

This is an article about immigration (with.Java).

I want to solve the coding test problem, find out how to solve it differently from the retrospective of the problem I solved, and get to know.

Let’s get to the problem first.

Problem

N people are waiting in line for immigration.

Each examiner at each immigration desk takes different time to examine.

At first, all the examination tables are empty.

Only one judge can be judged at the same time.

The person standing at the front can go to the empty screening table for a screening.

However, if there is a screening table that finishes faster, you can wait and go there for a screening.

I want to minimize the time it takes for everyone to be judged.

Number of people waiting for immigration, when given as parameters the array times that each examiner takes to examine one person, write a solution function to return the minimum amount of time it takes for everyone to be screened.

Restrictions

• There are more than one person and no more than 1,000,000 people waiting for immigration.
• Each examiner takes more than one minute and no more than 1,000,000 minutes.
• The number of examiners is not less than one but not more than 100,000.

Input/output Examples

problem solving

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = times[times.length - 1] * (long)n;

        while(left <= right){
            long mid = (left + right) / 2;
            long test_num = 0;
            for(int i = 0; i < times.length; i++){
                test_num += mid / times[i];
            }
            if(test_num < n){
                left = mid + 1;
            }else{
                answer = mid;
                right = mid - 1;
            }
        }
        return answer;
    }
}

Solution Description

Solve the problem of finding the minimum time for a given examiner to examine n persons in a given time.

For this, we use a binary search algorithm.

First, sort the times, the given time array, in ascending order.

This is a necessary step to set the minimum time and maximum time.

The left variable is then set to 0, and the right variable is set to be the time of the examiner (the last element in the times array) multiplied by n.

This is based on the assumption that the screening time takes up to the maximum.

While performing a binary search, set the mid value to an intermediate value between left and right.

mid is considered the current average time, and calculates how many people each examiner can judge within this time.

To do this, use the test_num variable to find the total number of people that all examiners can examine during mid time.

The test_num value is calculated by adding all the values of mid divided by each examiner’s review time.

Afterwards, if test_num is less than n, this means that not everyone can be judged within the current time (mid), so set the left to mid + 1 to allocate more time.

Conversely, if test_num is n or higher, this means that everyone can be judged within the current time (mid), so set answer to mid and right to mid-1 to see if it is possible to allocate less time.

Repeat this process until the left is greater than right.

Finally, answer stores a minimum amount of time for everyone to be judged.

The algorithm uses binary exploration to reduce time complexity and solve problems efficiently.