Given an array arr[][2] consisting of N pair of strings representing the starting and ending time (in 12 hours format) and a string P which represents the time of the meeting, the task is to find the count of intervals that contains the time P.
Examples:
Input: P = “12:01:AM”, arr[][2] = {{“12:00:AM”, “11:55:PM”}, {“12:01:AM”, “11:50:AM”}, {“12:30:AM”, “12:00:PM”}, {“11:57:AM”, “11:59:PM”}}
Output: 2
Explanation: The time P lies in the first and second time intervals.Input: P = “12:01:AM”, arr[][2] = {{“09:57:AM”, “12:00:PM”} }
Output: 0
Explanation: No interval contains the time P.
Approach: The idea is to first convert all the times from 12-hour format into 24-hour format and then compare the range with Time P. Follow the steps below to solve the problem:
- First, convert all the times of 12 hours format to 24 hours format and then store the integer value of 24 -hours time format.
- Initialize a variable, say ans, to store the count of intervals in which P lies.
- Traverse the array arr[] and increment the count of ans by 1 if (P ? L && P ? R) or (P ? R && P ? L).
- Finally, after completing the above steps, print ans.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to convert a time in 24// hour format to an equivalent integerint convert(string str){ // Removes ":" at 3rd position str.replace(2, 1, ""); // Calculate hours int h1 = (int)str[1] - '0'; int h2 = (int)str[0] - '0'; int hh = (h2 * 10 + h1 % 10); // Stores the time in 24 hours format int time = 0; // If time is in "AM" if (str[5] == 'A') { // If hh is equal to 12 if (hh == 12) time += stoi(str.substr(2, 2)); else { time += stoi(str.substr(0, 2)); } } // If time is in "PM" else { // If hh is equal to 12 if (hh == 12) { time += stoi(str.substr(0, 4)); } else { time += stoi(str.substr(0, 4)); time += 1200; } } // Return time return time;}// Function to count number// of intervals in which p liesint countOverlap(string arr[][2], int n, string p){ // Stores the count int ans = 0; // Stores the integer value of // 24 hours time format of P int M = convert(p); // Traverse the array for (int i = 0; i < n; i++) { // Stores the integer value of // 24 hours time format of arr[i][0] int L = convert(arr[i][0]); // Stores the integer value of // 24 hours time format of arr[i][1] int R = convert(arr[i][1]); // If M lies within the [L, R] if ((L <= M && M <= R) || (M >= R && M <= L)) // Increment ans by 1 ans++; } // Return ans return ans;}// Driver Codeint main(){ string arr[][2] = { { "12:00:AM", "11:55:PM" }, { "12:01:AM", "11:50:AM" }, { "12:30:AM", "12:00:PM" }, { "11:57:AM", "11:59:PM" } }; string P = "12:01:PM"; int N = sizeof(arr) / sizeof(arr[0]); cout << countOverlap(arr, N, P) << endl;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG { // Function to convert a time in 24 // hour format to an equivalent integer static int convert(String str) { // Removes ":" at 3rd position str = str.substring(0, 2) + str.substring(3); // Calculate hours int h1 = (int)str.charAt(1) - '0'; int h2 = (int)str.charAt(0) - '0'; int hh = (h2 * 10 + h1 % 10); // Stores the time in 24 hours format int time = 0; // If time is in "AM" if (str.charAt(5) == 'A') { // If hh is equal to 12 if (hh == 12) time += Integer.parseInt( str.substring(2, 4)); else { time += Integer.parseInt( str.substring(0, 2)); } } // If time is in "PM" else { // If hh is equal to 12 if (hh == 12) { time += Integer.parseInt( str.substring(0, 4)); } else { time += Integer.parseInt( str.substring(0, 4)); time += 1200; } } // Return time return time; } // Function to count number // of intervals in which p lies static int countOverlap(String arr[][], int n, String p) { // Stores the count int ans = 0; // Stores the integer value of // 24 hours time format of P int M = convert(p); // Traverse the array for (int i = 0; i < n; i++) { // Stores the integer value of // 24 hours time format of arr[i][0] int L = convert(arr[i][0]); // Stores the integer value of // 24 hours time format of arr[i][1] int R = convert(arr[i][1]); // If M lies within the [L, R] if ((L <= M && M <= R) || (M >= R && M <= L)) // Increment ans by 1 ans++; } // Return ans return ans; } // Driver Code public static void main(String[] args) { String[][] arr = new String[][] { { "12:00:AM", "11:55:PM" }, { "12:01:AM", "11:50:AM" }, { "12:30:AM", "12:00:PM" }, { "11:57:AM", "11:59:PM" } }; String P = "12:01:PM"; int N = arr.length; System.out.println(countOverlap(arr, N, P)); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program to implement the approach# Function to convert a time in 24# hour format to an equivalent integerdef convert(str): # Removes ":" at 3rd position str = str.replace(":", "", 1) # Calculate hours hh = int(str[0:2]) # Stores the time in 24 hours format time = 0 # If time is in "AM" if str[-1] == "A": # If hh is equal to 12 if hh == 12: time += int(str[2:4]) else: time += int(str[0:2]) # If time is in "PM" else: # If hh is equal to 12 if hh == 12: time += int(str[0:4]) else: time += int(str[0:4]) time += 1200 # Return time return time# Function to count number# of intervals in which p liesdef countOverlap(arr, n, p): # Stores the count ans = 0 # Stores the integer value of # 24 hours time format of P M = convert(p) # Traverse the array for i in range(n): # Stores the integer value of # 24 hours time format of arr[i][0] L = convert(arr[i][0]) # Stores the integer value of # 24 hours time format of arr[i][1] R = convert(arr[i][1]) # If M lies within the [L, R] if L <= M <= R : # Increment ans by 1 ans += 1 # Return ans return ans# Driver Codearr = [["12:00:AM", "11:55:PM"], ["12:01:AM", "11:50:AM"], ["12:30:AM", "12:00:PM"], ["11:57:AM", "11:59:PM"]]P = "12:01:PM"N = len(arr)print(countOverlap(arr, N, P)) |
C#
// C# implementation of the above approachusing System;class GFG{// Function to convert a time in 24// hour format to an equivalent integerstatic int convert(String str){ // Removes ":" at 3rd position str = str.Substring(0, 2) + str.Substring(3); // Calculate hours int h1 = (int)str[1] - '0'; int h2 = (int)str[0] - '0'; int hh = (h2 * 10 + h1 % 10); // Stores the time in 24 hours format int time = 0; // If time is in "AM" if (str[5] == 'A') { // If hh is equal to 12 if (hh == 12) time += Int32.Parse( str.Substring(2, 2)); else { time += Int32.Parse( str.Substring(0, 2)); } } // If time is in "PM" else { // If hh is equal to 12 if (hh == 12) { time += Int32.Parse( str.Substring(0, 4)); } else { time += Int32.Parse( str.Substring(0, 4)); time += 1200; } } // Return time return time;}// Function to count number// of intervals in which p liesstatic int countOverlap(String [,]arr, int n, String p){ // Stores the count int ans = 0; // Stores the integer value of // 24 hours time format of P int M = convert(p); // Traverse the array for(int i = 0; i < n; i++) { // Stores the integer value of // 24 hours time format of arr[i,0] int L = convert(arr[i,0]); // Stores the integer value of // 24 hours time format of arr[i,1] int R = convert(arr[i,1]); // If M lies within the [L, R] if ((L <= M && M <= R) || (M >= R && M <= L)) // Increment ans by 1 ans++; } // Return ans return ans;}// Driver Codepublic static void Main(String[] args){ String[,] arr = new String[,]{ { "12:00:AM", "11:55:PM" }, { "12:01:AM", "11:50:AM" }, { "12:30:AM", "12:00:PM" }, { "11:57:AM", "11:59:PM" } }; String P = "12:01:PM"; int N = arr.GetLength(0); Console.WriteLine(countOverlap(arr, N, P));}}// This code is contributed by 29AjayKumar |
Javascript
// JS program to implement the approachfunction convert(str) { // Removes ":" at 3rd position str = str.replace(":", "", 1); // Calculate hours const hh = parseInt(str.substring(0, 2)); // Stores the time in 24 hours format let time = 0; // If time is in "AM" if (str.charAt(str.length - 1) === "A") { // If hh is equal to 12 if (hh === 12) { time += parseInt(str.substring(2, 4)); } else { time += parseInt(str.substring(0, 2)); } } else { // If hh is equal to 12 if (hh === 12) { time += parseInt(str.substring(0, 4)); } else { time += parseInt(str.substring(0, 4)); time += 1200; } } // Return time return time;}function countOverlap(arr, n, p) { // Stores the count let ans = 0; // Stores the integer value of // 24 hours time format of P const M = convert(p); // Traverse the array for (let i = 0; i < n; i++) { // Stores the integer value of // 24 hours time format of arr[i][0] const L = convert(arr[i][0]); // Stores the integer value of // 24 hours time format of arr[i][1] const R = convert(arr[i][1]); // If M lies within the [L, R] if (L <= M && M <= R) { // Increment ans by 1 ans++; } } // Return ans return ans;}const arr = [ ["12:00:AM", "11:55:PM"], ["12:01:AM", "11:50:AM"], ["12:30:AM", "12:00:PM"], ["11:57:AM", "11:59:PM"],];const P = "12:01:PM";const N = arr.length;console.log(countOverlap(arr, N, P));// This code is contributed by phasing17 |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
