The Number of Full Rounds You Have Played

In a previous post I mentioned that I was planning on an elective surgery on my left knee. Due to the COVID-19 pandemic I had to postpone the procedure. Finally I had it done about three months ago. The procedure took about an hour but no matter how much I have done to get back to pre surgery, I feel I am about 95% there but there are a few things that are not there yet. Next week it will officially be three months since surgery so I am hopping to be 98% to 99% healed.

I have mentioned that I might switch to C++ for a while. Based on the progress on a set of books that I am reading, I might switch to Python for a couple months and then to C++.

In this post I will attempt to solve the problem LeetCode 1904 The Number of Full Rounds You Have Played.

A new online video game has been released, 
and in this video game, 
there are 15-minute rounds scheduled every quarter-hour period. 

This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, 
where HH represents an integer number from 00 to 23. 
A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" 
representing the exact time you started and finished playing the game, respectively, 
calculate the number of full rounds that you played during your game session.

o For example, if startTime = "05:20" and finishTime = "05:59" 
this means you played only one full round from 05:30 to 05:45. 
You did not play the full round from 05:15 to 05:30 because you started after the round began, 
and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, 
this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played 
if you had started playing at startTime and finished at finishTime.

Constraints:

o startTime and finishTime are in the format HH:MM.
o 00 <= HH <= 23
o 00 <= MM <= 59
o startTime and finishTime are not equal

Long description but the requirements come through well. We are given two times in 24-hour (military) time. We need to figure out how many rounds of a 15-minute game we can play. The important fact is that the games start at hh:00, HH:15, HH:30 and HH:45 each hour. As an example, if we start playing at 13:07 and end at 14:00, we would play three rounds because the first game would start at 13:15, the second at 13:30 and the third and last at 13:45. Note that if we leave a few minutes earlier e.g., 13:56, then we would only play two rounds because we did not played the full 15 minutes of the last game.

12:34
12:34
main <<<  startTime ==>12:34<==
main <<< finishTime ==>12:34<==
main <<< rounds: 0


12:01
12:44
main <<<  startTime ==>12:01<==
main <<< finishTime ==>12:44<==
main <<< rounds: 1


12:01
12:17
main <<<  startTime ==>12:01<==
main <<< finishTime ==>12:17<==
main <<< rounds: 0


20:00
06:00
main <<<  startTime ==>20:00<==
main <<< finishTime ==>06:00<==
main <<< rounds: 40


00:00
23:59
main <<<  startTime ==>00:00<==
main <<< finishTime ==>23:59<==
main <<< rounds: 95


22:46
23:01
main <<<  startTime ==>22:46<==
main <<< finishTime ==>23:01<==
main <<< rounds: 0


00:47
00:57
main <<<  startTime ==>00:47<==
main <<< finishTime ==>00:57<==
main <<< rounds: 0


00:47
01:07
main <<<  startTime ==>00:47<==
main <<< finishTime ==>01:07<==
main <<< rounds: 0

We will write our own test scaffold. It is simpler if you just use the on-line IDE provided by LeetCode. In this post we will write a simple test scaffold. The code will be implemented in Java using the VSCode IDE on a Windows computer.

We are provided with two times on two separate lines. The start time is in the first line and the finish time in the second line.

Our test scaffold seems to read the two times and display them to make sure all is well so far. The function of interest is called and the result displayed.

    public int numberOfRounds(String startTime, String finishTime) {
        
    }

The signature for our function of interest takes as arguments the `startTime` and the `finishTime`. The function needs to compute the number of rounds played. The returning value is displayed.

     /**
      * Test scaffold
      * @throws IOException
      */
      public static void main(String[] args) throws IOException {
          
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read start time ****
        String startTime = br.readLine().trim();

        // **** read finish time ****
        String finishTime = br.readLine().trim();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<<  startTime ==>" + startTime + "<==");
        System.out.println("main <<< finishTime ==>" + finishTime + "<==");

        // **** call function of interest and display result ****
        System.out.println("main <<< rounds: " + numberOfRounds(startTime, finishTime));
      }

The test code is simple. The two strings representing the times are read and passed to the function of interest. The result generate by our function is then displayed.

    /**
     * Utility function.
     * 
     * !!!! NOT PART OF SOLUTION !!!!
     */
    static int normalizeTime (String str, boolean start) {

        // **** convert hours to minutes ****
        String[] hm = str.split(":");
        int mins = Integer.parseInt(hm[0]);
        mins *= 60;

        // **** compensate for 15 minute intervals ****
        int m = Integer.parseInt(hm[1]);
        while (m % 15 != 0) {
            if (start)
                m += 1;
            else 
                m -= 1;
        }

        // **** update number of minutes ****
        return mins += m;
    }

I figured that the best approach would be to convert the times to minutes. I decided to write the `normalizeTime` auxiliary function and give it a try. After a few minutes it was clear that some test cases made it but some did not. That is when the brute force approach came into play.

    /**
     * A new online video game has been released, 
     * and in this video game, 
     * there are 15-minute rounds scheduled every quarter-hour period. 
     * 
     * This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, 
     * where HH represents an integer number from 00 to 23. 
     * A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.
     * 
     * Given two strings startTime and finishTime in the format "HH:MM" 
     * representing the exact time you started and finished playing the game, respectively, 
     * calculate the number of full rounds that you played during your game session.
     * 
     * Runtime: 1 ms, faster than 63.86% of Java online submissions
     * Memory Usage: 37.2 MB, less than 76.67% of Java online submissions.
     * 
     * Time:  O(1414 * 2)  Space: O(1)
     */
    static int numberOfRounds (String startTime, String finishTime) {

        // **** sanity check(s) ****
        if (startTime.equals(finishTime)) return 0;

        // **** initialization ****
        int rounds = 0;

        // **** convert start time to minutes ****
        int st = stringToMinutes(startTime);

        // **** convert finish time to minutes ****
        int ft = stringToMinutes(finishTime);

        // **** compute difference in minutes ****
        if (ft > st) {

            // ???? ????
            // System.out.println("<<< ft: " + ft + " > st: " + st);

            // **** current day ****
            for (int t = 0; t < (24 * 60); t += 15) {

                // **** count this round ****
                if (st <= t && ft >= (t + 15)) {

                    // **** increment round count ****
                    rounds++;

                    // ???? ????
                    // System.out.println("<<<  t: " + t + " rounds: " + rounds);
                }
            }
        } else {

            // ???? ????
            // System.out.println("<<< ft: " + ft + " <= st: " + st);

            // **** previous day ****
            for (int t = 0; t < (24 * 60); t += 15) {

                // **** count this round ****
                if (st <= t && (24 * 60) >= (t + 15)) {

                    // **** increment round count ****
                    rounds++;

                    // ???? ????
                    // System.out.println("<<<  t: " + t + " rounds: " + rounds);
                }
            }

            // **** current day ****
            for (int t = 0; t < (24 * 60); t += 15) {

                // **** count this round ****
                if (0 <= t && ft >= (t + 15)) {

                    // **** increment round count ****
                    rounds++;

                    // ???? ????
                    // System.out.println("<<<  t: " + t + " rounds: " + rounds);
                }
            }
        }
        
        // **** return the number of rounds ****
        return rounds;
    }

We start by converting the `startTime` and `finishTime` to minutes. This provides us with a time interval. The problem is that if we start playing late in the day and finish early morning, things get a little complicated. The `finishTime` would be smaller than the `startTime`.

The code is split into two parts. The first deals with the case when the `finishTime` is larger than the `startTime`.

We enter a loop in which we increment time in 15-minute increments. We loop from 00:00 to 00:00 which represents 24-hours in minutes (24 *60) using 15-minute increments.

We check if the `startTime` was prior to the 15-minutes and the `finalTime` is greater or equal that the current time + 15. If so, we increment the number of rounds by one and repeat.

The second case is when the `startTime` is larger than the `finishTime`. We split the two days. We start by processing the first day as we did in the previous case. The difference is that we end at 24:00 or 00:00.

We then repeat for the next day that starts at 00:00 and could end at 24:00 or 00:00.note that the time for the rounds is slightly different than in the first day.

When all is said and done, we return the number of rounds played.

    /**
     * Compute the number of minutes since the start of the day in minutes.
     * 
     * Utility function.
     */
    static int stringToMinutes (String str) {
        String[] hm = str.split(":");
        int mins = Integer.parseInt(hm[0]);
        mins *= 60;
        mins += Integer.parseInt(hm[1]);
        return mins;
    }

This function is used to convert the strings holding the `startTime` and `finishTime` to minutes.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.