C++ Coding Test Course, Creating Blu-ray

Hello! In this post, we will deeply explore the topic of ‘Creating Blu-ray’ by solving algorithm problems in preparation for C++ coding tests. This problem can primarily be approached using dynamic programming and binary search. Let’s write some code together and follow the step-by-step process of solving the problem.

Problem Description

A Blu-ray is a disc that stores and plays media content such as movies. A user is given a specific list of movies, and we aim to store these movies on Blu-ray as efficiently as possible. The user can set a maximum time for each Blu-ray, and we will minimize the number of Blu-rays needed using this constraint.

Problem Definition

    The list of movies consists of N movies, with the length of each movie given as A[i]. Now, we want to store all the movies using Blu-ray limited by duration T with the minimum number of Blu-rays.
    Let's solve the problem of calculating the number of Blu-rays using the given constraints algorithmically.

Input

  • The first line contains the number of movies N (1 ≤ N ≤ 1000) and the maximum time T (1 ≤ T ≤ 10000) that can be stored on a Blu-ray.
  • The second line provides N integers representing the length of each movie. The length of each movie is between 1 and T.

Output

Print the minimum number of Blu-rays required.

Problem Approach

To solve the problem, we follow these steps:

  1. Utilize binary search to set the range of possible maximum storage time for the Blu-ray.
  2. Count the number of Blu-rays needed to store the movies on each Blu-ray.
  3. If the time exceeds T, increase the number of Blu-rays; if it is within T, adjust the maximum Blu-ray storage time.
  4. Finally, print the required number of Blu-rays.

Code Implementation

    
    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int countBluRays(const vector<int>& movies, int maxTime) {
        int count = 1; // At least 1 Blu-ray is needed
        int currentTime = 0;

        for (int movie : movies) {
            if (currentTime + movie > maxTime) {
                count++; // A new Blu-ray is needed
                currentTime = movie; // Assign current movie
            } else {
                currentTime += movie; // Add movie to the current Blu-ray
            }
        }
        return count;
    }

    int main() {
        int N, T;
        cin >> N >> T;

        vector<int> movies(N);
        for (int i = 0; i < N; i++) {
            cin >> movies[i];
        }

        // Determine the maximum time for Blu-ray using binary search
        int low = *max_element(movies.begin(), movies.end());
        int high = accumulate(movies.begin(), movies.end(), 0);
        int result = high;

        while (low <= high) {
            int mid = (low + high) / 2;
            int requiredBluRays = countBluRays(movies, mid);

            if (requiredBluRays <= T) {
                result = mid; // We can reduce the maximum time for Blu-ray
                high = mid - 1;
            } else {
                low = mid + 1; // Increase the maximum time for Blu-ray
            }
        }

        cout << result << endl;
        return 0;
    }

Code Explanation

The code above consists of the following main parts:

  1. countBluRays function: Calculates the number of Blu-rays needed to store the movies based on the given maximum Blu-ray time (maxTime). It iterates through each movie to check if it can be added to the current Blu-ray and adds a Blu-ray if needed.
  2. main function: Receives the number of movies N and the maximum time T for the Blu-ray, then stores the lengths of the movies. It then finds the minimum Blu-ray time needed to store all movies using binary search.

Algorithm Complexity

The time complexity of the algorithm is O(N log S). Here, N is the number of movies, and S is the sum of movie lengths. The binary search process requires iterating through all movies each time, making it efficient.

Conclusion

In this post, we easily understood the basics of binary search and dynamic programming through the coding problem ‘Creating Blu-ray’. It is essential to grasp the essence of the problem and find an appropriate approach when solving algorithmic problems. As experience builds through practice, solving more complex problems will become easier. In the next post, we will explore more diverse problems!

© 2023 C++ Coding Test Course