2446. Determine if Two Events Have Conflict

EasyArrayString
Leetcode Link

Problem Description

The problem presents us with a scenario where two events are happening on the same day and we want to determine if they conflict with each other. Each event provides a start time and an end time in 24-hour format (HH:MM). A conflict is defined as the presence of a common time interval between the two events, even if it's just a minute. For example, if event1 ends at 12:00 and event2 starts at 12:00, there is no conflict, but if event2 starts even one minute before event1 ends, there is a conflict. We are required to return true if there's a conflict and false otherwise.

Intuition

To determine if there is a conflict, we need to compare the time intervals of the two events. There are a few scenarios where no conflict can exist, which are important to identify.

  1. The first event ends before the second event starts. In this case, endTime1 is less than startTime2, so there is no overlap.
  2. The second event ends before the first event starts. Here, endTime2 is less than startTime1, and again, there is no overlap.

The solution cuts straight to the heart of these scenarios. It performs a simple logical check to see if the two time periods don't overlap. If the start time of event1 is after the end time of event2 or the end time of event1 is before the start time of event2, then the two events can't possibly conflict; they are entirely separate in time. This can be written concisely as:

1not (event1[0] > event2[1] or event1[1] < event2[0])

This expression evaluates to True if there is a conflict (event times overlap) and False if there is no conflict. The not operator negates the condition of no overlap, giving us the correct condition for detecting a conflict.

The elegance of the solution lies in its simplicity and the fact that it covers all possible scenarios where a conflict could arise with only one line of logical comparison.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Solution Approach

The solution to the problem uses a simple comparison-based approach, which falls under the category of interval scheduling algorithms. Interval scheduling problems typically involve finding optimum schedules among a set of events based on their start and end times. However, in this scenario, the task is not to schedule but to determine if there is an overlap between the two given intervals.

The data structures used in the solution are minimal—it simply takes the input in the form of two lists, event1 and event2, which consist of string elements representing the start and end times of the events.

The code uses a single Boolean expression to identify the condition where no conflict occurs. Here's a walkthrough of that logic:

1class Solution:
2    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
3        # Return False if event1 ends before event2 starts or vice versa
4        return not (event1[0] > event2[1] or event1[1] < event2[0])

Let's dissect the code:

  • event1[0] > event2[1]: This comparison checks if the start time of event1 is greater than the end time of event2. If this is true, it means event1 starts after event2 has ended, thus no conflict exists.

  • event1[1] < event2[0]: Conversely, this comparison checks if the end time of event1 is lesser than the start time of event2. This condition suggests that event1 ends before event2 starts, also indicating no conflict.

The or operator is used to combine these two comparisons. If either condition is true, there is no overlap; thus, event1 and event2 do not conflict.

The not operator at the beginning negates the result of the combined condition. If there is no overlap, the not operator turns the result to False, indicating no conflict. If there is an overlap (meaning both comparisons are false), the not operation turns the result to True, signaling a conflict.

There are no special algorithms or advanced data structures necessary for this solution, thanks to the simplicity of the problem. It relies on basic comparisons and logical operators to evaluate the conditions efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have two events:

  • event1 starts at 09:30 and ends at 11:00
  • event2 starts at 10:45 and ends at 12:30

Using the 24-hour format, here's how the events look:

  • event1 is represented as ['09:30', '11:00']
  • event2 is represented as ['10:45', '12:30']

To determine if there is a conflict between event1 and event2, we'll use the following logic from the solution approach:

1def haveConflict(event1: List[str], event2: List[str]) -> bool:
2    return not (event1[0] > event2[1] or event1[1] < event2[0])
  • First, we check if event1 starts after event2 ends; in our case, does '09:30' > '12:30'?. This is not true.
  • Second, we check if event1 ends before event2 starts; does '11:00' < '10:45'?. This is also not true.

Since neither of the conditions for no conflict is met (because both comparisons returned false), the combined result of the comparisons within the parentheses is False.

By applying the not operator, the resultant value becomes True, indicating that there is a conflict. In this case, event1 ends at 11:00, which is after event2 has started at 10:45, thus they share a time overlap from 10:45 to 11:00.

Therefore, when we input the given times into the function:

1event1 = ['09:30', '11:00']
2event2 = ['10:45', '12:30']
3
4print(haveConflict(event1, event2)) # Output: True

The output is True, reflecting that there is a conflict between these two events.

Solution Implementation

1from typing import List
2
3class Solution:
4    def have_conflict(self, event1: List[str], event2: List[str]) -> bool:
5        """
6        Check if two events conflict based on their start and end times.
7
8        Args:
9        event1 (List[str]): The Start and end time of the first event [start, end]
10        event2 (List[str]): The Start and end time of the second event [start, end]
11
12        Returns:
13        bool: True if there is a conflict between the events, False otherwise.
14        """
15        # Convert the start and end times to a comparable format if necessary
16        # Assuming event1 and event2 are in correct format and no conversion is needed.
17
18        # The events do not conflict if event1 ends before event2 starts
19        # or if event1 starts after event2 ends. Otherwise, they do conflict.
20        return not (event1[1] < event2[0] or event1[0] > event2[1])
21
22# Example Usage
23sol = Solution()
24# Assuming the times are in 'HH:MM' format and events are ['start time', 'end time']
25print(sol.have_conflict(["09:00", "10:00"], ["10:01", "11:00"])) # Should print False, no conflict
26print(sol.have_conflict(["09:00", "10:00"], ["09:30", "10:30"])) # Should print True, there is a conflict
27
1class Solution {
2
3    /**
4     * Check if two events have a conflict based on their start and end times.
5     *
6     * @param event1 Array with 2 strings representing the start and end times of the first event.
7     * @param event2 Array with 2 strings representing the start and end times of the second event.
8     * @return boolean value that indicates whether the events conflict.
9     */
10    public boolean haveConflict(String[] event1, String[] event2) {
11        // Event 1 ends before Event 2 starts -> No conflict
12        boolean event1EndsBeforeEvent2Starts = event1[1].compareTo(event2[0]) < 0;
13      
14        // Event 1 starts after Event 2 ends -> No conflict
15        boolean event1StartsAfterEvent2Ends = event1[0].compareTo(event2[1]) > 0;
16      
17        // If either of the above conditions is true, 
18        // there is no conflict, so we return the negation of any conflict.
19        return !event1EndsBeforeEvent2Starts && !event1StartsAfterEvent2Ends;
20    }
21}
22
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to check if two events have a conflict based on their time ranges
7    bool haveConflict(std::vector<std::string>& event1, std::vector<std::string>& event2) {
8        // event1: [start_time1, end_time1]
9        // event2: [start_time2, end_time2]
10      
11        // Convert event's start and end times to comparable strings
12        std::string start_time1 = event1[0];
13        std::string end_time1 = event1[1];
14        std::string start_time2 = event2[0];
15        std::string end_time2 = event2[1];
16      
17        // Compare the times to determine if there is a conflict
18        // No conflict if event1 ends before event2 starts or event1 starts after event2 ends
19        return !(end_time1 < start_time2 || start_time1 > end_time2);
20    }
21};
22
1// Function to determine if two events have a conflict based on their time intervals.
2// @param event1 The time interval of the first event as an array with start and end times.
3// @param event2 The time interval of the second event as an array with start and end times.
4// @returns A boolean value indicating whether there is a conflict (true) or not (false).
5function haveConflict(event1: string[], event2: string[]): boolean {
6    // Check if the first event ends before the second event starts or
7    // the first event starts after the second event ends.
8    // If either condition is true, there is no conflict.
9    const event1StartsAfterEvent2Ends: boolean = event1[0] > event2[1];
10    const event1EndsBeforeEvent2Starts: boolean = event1[1] < event2[0];
11  
12    // Return the inverse of either condition.
13    // If both conditions are false (meaning there is overlap), the result is true (conflict exists).
14    return !(event1StartsAfterEvent2Ends || event1EndsBeforeEvent2Starts);
15}
16
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

Time Complexity

The time complexity of the function haveConflict is O(1). This is because the function performs a constant number of operations regardless of the input size. It compares the start and end times of two events, which involves just a few comparisons and logical operations.

Space Complexity

The space complexity of the function haveConflict is also O(1). The function does not use any additional data structures that grow with the input size. It only uses a fixed amount of space to store the input parameters and perform the comparison operations.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫