Leetcode 2446. Determine if Two Events Have Conflict

Posted on In ,

题目描述

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.

 

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:

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

解答

Naive Solution

It's my first try which I manually convert the input from string to int.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int char2num(int c) {return (c-'0');};
    int string2time(string &s)
    {
        return(char2num(s[0])*1000+char2num(s[1])*100+char2num(s[3])*10+char2num(s[4]));
    }
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        int s1=string2time(event1[0]),e1=string2time(event1[1]),
            s2=string2time(event2[0]),e2=string2time(event2[1]);
        if (s1<=s2 && s2<=e1)
            return (true);
        if (s1<=e2 && e2<=e1)
            return (true);
        if (s2<=s1 && s1<=e2)
            return true;
        if (s2<=e1 && e1<=e2)
            return true;
        return(false);
    }
};

Standard Solution

Directly compare the strings. And note that it's easier to represent the non-conflict situations. 

1
2
3
4
5
6
class Solution {
public:
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        return !(event1[1]<event2[0] || event2[1]<event1[0]);
    }
};

Complexity

  • Time: \(O(1)\)
  • Space: \(O(1)\)

题外话

Please notice that lexicographical_compare is designed for comparing containers, e.g. vector and string.