JavaScript Coding Test Course, Creating Blu-ray

Hello! In this blog post, we will discuss an algorithm problem to prepare for the JavaScript coding test. The topic is ‘Creating Blu-rays’. The problem is to find the minimum number of Blu-rays needed to create the given movies. To solve this, we will need to utilize binary search and the greedy algorithm.

Problem Description

You want to create multiple movies on Blu-ray. The running time of each movie is given, and a Blu-ray can hold up to K amount of time. Your goal is to minimize the number of Blu-rays to store all the movies. However, each Blu-ray must contain movies such that their total running time does not exceed K.

Input

  • The first line contains N and K. (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10^6)
  • The second line contains N natural numbers separated by spaces, representing the running times of each movie. (1 ≤ movie running time ≤ 10^6)

Output

Print the minimum number of Blu-rays.

Example

Input:
4 5
2 3 1 4

Output:
2

Problem Solving Process

To approach this problem, we can proceed in the following steps.

Step 1: Understand the Problem

Consider how to allocate the given movies into Blu-rays with a maximum running time of K. Since the running times of each movie are provided, we need to consider how to combine them without exceeding K.

Step 2: Derive Ideas

Since we cannot simply fit all movies into one Blu-ray, we will iteratively explore the movie list to check if they can fit into each Blu-ray. To do this, we will use binary search to find the minimum number of Blu-rays needed.

Step 3: Exception Handling

If the time to fit a movie exceeds K, we must place that movie on a new Blu-ray. It is important to be mindful of this condition to fit as many movies as possible into Blu-rays.

Step 4: Algorithm Implementation

Now, we will implement a JavaScript function based on the above ideas.


function minBluRays(N, K, movies) {
    let bluRays = 0;
    let currentTime = 0;

    for (let i = 0; i < N; i++) {
        if (currentTime + movies[i] > K) {
            bluRays++;
            currentTime = movies[i];
        } else {
            currentTime += movies[i];
        }
    }

    if (currentTime > 0) {
        bluRays++;
    }

    return bluRays;
}

// Example execution
const N = 4;
const K = 5;
const movies = [2, 3, 1, 4];
console.log(minBluRays(N, K, movies)); // Output: 2

Conclusion

In this article, we demonstrated the process of solving a commonly encountered algorithm problem in JavaScript coding tests through the ‘Creating Blu-rays’ problem. Understanding the essence of the problem and finding the necessary algorithms is very important. It is advisable to utilize the given time well to write efficient code.

I hope this problem helps you develop a basic understanding of JavaScript and an algorithmic mindset. Thank you!