Count the number of intervals that intersect a given meeting time

Problem Statement

We have been given a two-dimensional array containing start and end time pairs, representing a 12-hour time interval. At the same time, we are also given a string str expressed in 12-hour time. We need to find the total number of intervals that contain the time represented by str.

ExampleExample

enter

arr[][2] = {{“12:02:AM”, “10:55:PM”}, 
{“12:51:AM”, “11:40:AM”}, 
{“01:30:AM”, “12:00:PM”}, 
{“11:57:PM”, “11:59:PM”}}, 
str = “2:30:AM”

Output

3

Explanation

Explanation

The time "2:30:AM" intersects the previous three time intervals.

enter

arr[][2] = {{“01:02:PM”, “10:55:PM”}, 
{“01:30:AM”, “11:00:AM”}}, str = “11:30:PM”

Output

0

Explanation

Explanation

The time "11:30:PM" does not intersect with any time interval given in the array.

method one

In this method we will convert the time to 24 hour format. We will then calculate the total number of time intervals that intersect the given time by comparison. Furthermore, we will use the substr() method to get the substring and the stoi() method to convert the string to an integer.

algorithm

• Step 1 - Define the convertTime() function to convert time to 24-hour format.

• Step 1.1 − Use the replace() method to replace the colon in the third position with an empty string.

• Step 1.2 − Get the first and second characters representing the hour from the given string and multiply the first number by 10 plus the second number to convert it to hours.

• Step 1.3 - Initialize the 'time_24' variable to zero.

• Step 1.4 − We need to handle two situations to convert the time to 24-hour format. The first case is in the morning and the second case is in the afternoon.

• Step 1.4.1 - If the 5th character in the string is 'A', then the time is AM. If the time is AM and the hour is equal to 12, only the minutes are extracted from the string because we consider 12:00 AM as the 00:00 hour. Otherwise, convert the time string to an integer value.

• Step 1.4.2 - If the fifth character in the string is 'P', then the time is afternoon. Extract a time string and convert it to an integer. Additionally, if the hour is not equal to 12, 1200 is added to the 'time_24' variable.

• Step 2 - The convertTime() function will return the time in the following format.

  • 12:00:AM = 0000

  • 12:58:AM = 0059

  • 11:32:AM = 1132

  • 11:32:PM = 1200 1132 = 2332

  • 04:56:PM = 1200 456 = 1656

  • If the 5th character in the string is 'A', the time is morning. If the time is AM and the hour is equal to 12, only the minutes are extracted from the string because we consider 12:00 AM as the 00:00 hour. Otherwise, convert the time string to an integer value.

• Step 3 - Convert the given time string to 24-hour format.

• Step 4 - Use a for loop to traverse the time interval array and convert each time string to a 24-hour format.

• Step 5 - Meanwhile, continue checking if the given time string is between the current interval. If so, increase the count of 'res' by 1.

• Step 6 - Return the value of the ‘res’ variable.

Example

Example

#include <bits/stdc++.h>
using namespace std;
// Function to convert the given time_24 in 24 hours format
int convertTime(string str){
   // Remove the colon from the string
   str.replace(2, 1, "");
   // Stores the hour
   int char_h1 = (int)str[1] - '0';
   int char_h2 = (int)str[0] - '0';
   int hours = (char_h2 * 10 + char_h1 % 10);
   // variable to store the time in 24 hours format
   int time_24 = 0;
   // If the time is in "AM."
   if (str[5] == 'A'){
      // If hours are equal to 12, then update it to 0 as 12 AM, and only minutes to time_24
      if (hours == 12){
         time_24 += stoi(str.substr(2, 2));
      } else {
         // add hours and minutes to time_24
         time_24 += stoi(str.substr(0, 4));
      }
   }
   // If time is in "PM"
   else {
      // If hours is equal to 12, add time as it is to time_24
      if (hours == 12){
         time_24 += stoi(str.substr(0, 4));
      } else {
         // add time to time_24
         time_24 += stoi(str.substr(0, 4));
         // add 1200 = 12 : 00 PM to time_24 to convert in 24 hours format.
         time_24 += 1200;
      }
   }
   return time_24;
}
// Function to find the total number of intervals that intersects with given meeting time_24
int totalIntersects(string arr[][2], int len, string str){
   // to store the total number of intervals
   int res = 0;
   // convert the given time_24 in 24 hours format
   int convertedStr = convertTime(str);
   // Traverse the array
   for (int i = 0; i < len; i++){
      // convert the starting time_24 of the current interval in 24-hour format
      int initial = convertTime(arr[i][0]);
      // convert the ending time_24 of the current interval in 24-hour format
      int end = convertTime(arr[i][1]);
      // If the given time_24 lies in the interval [initial, end], then increment res by 1
      if ((initial <= convertedStr && convertedStr <= end) || (convertedStr >= end && convertedStr <= initial))
         res++;
   }
   // Return res
   return res;
}
int main(){
   string arr[][2] = {{"11:00:AM", "11:55:PM"},
                       {"12:19:AM", "9:30:AM"},
                       {"12:51:AM", "12:59:PM"},
                       {"6:57:AM", "7:50:PM"}};
   string str = "12:54:AM";
   int len = sizeof(arr) / sizeof(arr[0]);
   cout << "The total number of the interval that intersects with given meeting time_24 are - " << totalIntersects(arr, len, str) << endl;
}

Output

The total number of the interval that intersects with given meeting time_24 are - 2

• Time Complexity - O(N) since we iterate over the array of time intervals.

• Space complexity − O(1), because we don’t use constant space.

When solving the above problem, the user should mainly focus on converting the time to 24-hour format, and then just do the normal comparison.

The above is the detailed content of Count the number of intervals that intersect a given meeting time. For more information, please follow other related articles on the PHP Chinese website!