Skip to main content

Determine if Two Events Have Conflict

Problem Statement​

Problem Description​

You are given two arrays of strings that represent two inclusive events that happened on the same day, event1 and event2, where:

event1 = [startTime1, endTime1] and event2 = [startTime2, endTime2]. Event times are valid 24 hours format in the form of HH:MM.

A conflict happens when two events have some non-empty intersection (i.e., some moment is common to both events).

Return true if there is a conflict between two events. Otherwise, return false

Examples​

Example 1​

Input: event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
Output: true
Explanation: The two events intersect at time 2:00.

Example 2​

Input: event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]
Output: true
Explanation: The two events intersect starting from 01:20 to 02:00.

Example 3​

Input: event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]
Output: false
Explanation: The two events do not intersect.

Constraints​

  • event1.length == event2.length == 2
  • event1[i].length == event2[i].length == 5
  • startTime1 <= endTime1
  • startTime2 <= endTime2
  • All the event times follow the HH:MM format.

Solution of Given Problem​

Intuition and Approach​

The problem can be solved using a brute force approach or an optimized Technique.

Approach 1:Brute Force (Naive)​

Brute Force Approach:

  • Convert the event times to minutes since midnight.
  • Generate all the minutes for both events.
  • Check if there is any common minute between the two sets.

Codes in Different Languages​

Written by @AmruthaPariprolu
#include <vector>
#include <string>

using namespace std;

int toMinutes(const string& time) {
int hours = stoi(time.substr(0, 2));
int minutes = stoi(time.substr(3, 2));
return hours * 60 + minutes;
}

bool haveConflictBruteForce(vector<string>& event1, vector<string>& event2) {
int start1 = toMinutes(event1[0]);
int end1 = toMinutes(event1[1]);
int start2 = toMinutes(event2[0]);
int end2 = toMinutes(event2[1]);

for (int t1 = start1; t1 <= end1; ++t1) {
for (int t2 = start2; t2 <= end2; ++t2) {
if (t1 == t2) return true;
}
}
return false;
}


Complexity Analysis​

  • Time Complexity: O((end1−start1)∗(end2−start2))O((end1 - start1) * (end2 - start2))
  • We generate and check all possible minute pairs within the intervals.
  • Space Complexity: O(1)O(1)
  • We use a constant amount of extra space.

Video Explanation of Given Problem​


Authors:

Loading...