Leetcode 2446: Determine if Two Events Have Conflict
Given two events, each with a start time and end time in the HH:MM format, determine if the two events overlap at any point in time. Return
true
if there is any overlap, otherwise return false
.Problem
Approach
Steps
Complexity
Input: Each input consists of two arrays, `event1` and `event2`. Both arrays have two string elements representing the start and end times of the respective events.
Example: event1 = ["09:00","10:00"], event2 = ["09:30","11:00"]
Constraints:
• event1.length == event2.length == 2
• event1[i].length == event2[i].length == 5
• startTime <= endTime
Output: Return `true` if there is a conflict, meaning the two events overlap in time. Otherwise, return `false`.
Example: Output: true
Constraints:
• Both input arrays are guaranteed to have exactly two elements each, representing valid time intervals.
Goal: Determine if there is an overlap between two time intervals.
Steps:
• 1. Compare the start and end times of both events.
• 2. If the start time of the second event is before or at the end time of the first event, and the end time of the second event is after or at the start time of the first event, then the events overlap.
Goal: Time intervals are given in the valid 24-hour HH:MM format.
Steps:
• startTime1 <= endTime1
• startTime2 <= endTime2
• 0 <= startTime1, startTime2 <= 23:59
• endTime1, endTime2 <= 23:59
Assumptions:
• The events are within the same day, and the times are given in valid 24-hour format.
• Input: event1 = ["01:00","02:00"], event2 = ["01:30","03:00"]
• Explanation: The events overlap from 01:30 to 02:00, so the answer is `true`.
• Input: event1 = ["12:00","13:00"], event2 = ["14:00","15:00"]
• Explanation: The events do not overlap, so the answer is `false`.
Approach: The approach involves comparing the time intervals of both events to check if there is any overlap.
Observations:
• If the start time of one event is before or at the end time of the other event, and the end time is after or at the start of the other event, the two events overlap.
• This problem can be solved with simple comparisons of the start and end times of the two events.
Steps:
• 1. Extract the start and end times from both events.
• 2. Compare the start and end times of both events to determine if they overlap.
• 3. Return `true` if the events overlap, otherwise return `false`.
Empty Inputs:
• Input will not contain empty arrays as per the problem constraints.
Large Inputs:
• Event times are always within the valid 24-hour range, so we don't need to worry about very large numbers.
Special Values:
• When the start time and end time of both events are the same, the events will overlap, and the result should be `true`.
Constraints:
• The time format is always valid, so no need for further validation.
bool haveConflict(vector<string>& event1, vector<string>& event2) {
if(event2[0] <= event1[1] && event2[1] >= event1[0]) return true;
return false;
}
1 : Function Definition
bool haveConflict(vector<string>& event1, vector<string>& event2) {
This line defines the function `haveConflict` that takes two arguments, `event1` and `event2`, each representing a range of event start and end times.
2 : Conditional Check
if(event2[0] <= event1[1] && event2[1] >= event1[0]) return true;
This condition checks if the start time of `event2` is before or at the end time of `event1`, and if the end time of `event2` is after or at the start time of `event1`. If both conditions are true, it indicates a conflict.
3 : Return Statement
return false;
If no conflict is found, the function returns `false`.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant as we only need to compare the two time intervals.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we do not use additional data structures that grow with the input.
LeetCode Solutions Library / DSA Sheets / Course Catalog |
---|
comments powered by Disqus