Determine if Two Events Have Conflict
EasyPrompt
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]andevent2 = [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.
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 == 2event1[i].length == event2[i].length == 5startTime1 <= endTime1startTime2 <= endTime2- All the event times follow the
HH:MMformat.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves converting the time strings from the "HH:MM" format into a numerical representation, specifically the total number of minutes from midnight. This transformation allows for straightforward numerical comparison of the time intervals.
Algorithm
- Define a helper function
convertToMinutes(timeStr)that parses a "HH:MM" string and returns the total minutes from midnight (HH * 60 + MM). - Call this function to convert the start and end times of both
event1andevent2into four integer variables:start1,end1,start2,end2. - An overlap occurs if
event1does not end beforeevent2starts ANDevent2does not end beforeevent1starts. - This translates to the boolean condition:
start1 <= end2 && start2 <= end1. - Return the result of this comparison.
Walkthrough
The core idea is to handle time as a single integer value, which simplifies comparisons. A time "HH:MM" can be converted to HH * 60 + MM minutes.
We apply this conversion to the start and end times of both events. Let's say event1 becomes [s1, e1] and event2 becomes [s2, e2], where these are all integer values representing minutes.
Two events conflict if their time intervals overlap. Two intervals [s1, e1] and [s2, e2] overlap if and only if the start of one is before or at the same time as the end of the other, for both events. Mathematically, this is expressed as s1 <= e2 AND s2 <= e1.
Here is the implementation:
class Solution { public boolean haveConflict(String[] event1, String[] event2) { int start1 = convertToMinutes(event1[0]); int end1 = convertToMinutes(event1[1]); int start2 = convertToMinutes(event2[0]); int end2 = convertToMinutes(event2[1]); // Check for overlap condition: start1 <= end2 AND start2 <= end1 return start1 <= end2 && start2 <= end1; } private int convertToMinutes(String time) { // "HH:MM" int hours = Integer.parseInt(time.substring(0, 2)); int minutes = Integer.parseInt(time.substring(3, 5)); return hours * 60 + minutes; }}Complexity
Time
O(1) - The number of operations is constant. We perform a fixed number of string manipulations (substring), integer conversions (parseInt), arithmetic operations, and comparisons, none of which depend on the size of the input.
Space
O(1) - We use a few integer variables to store the converted times. The space used does not scale with the input size.
Trade-offs
Pros
The logic is very clear, explicit, and easy to understand.
This approach is robust and can be easily adapted if calculations involving time durations are needed.
Cons
Involves string parsing and integer conversions, which might have slightly more computational overhead than direct string comparison.
Solutions
Solution
class Solution {public boolean haveConflict(String[] event1, String[] event2) { return !(event1[0].compareTo(event2[1]) > 0 || event1[1].compareTo(event2[0]) < 0); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.