会议冲突算法

Question

今天我参加了一次面试，被问到如何检查两个会议是否冲突。每个会议都有开始时间和结束时间。 我尝试回答问题，但不是很具体...有人能提供些想法吗？

bool IsConflict(Datetime s1, Datetime e1, Datetime s2, Datetime e2)

如果存在冲突，应该返回True，如果没有冲突，则返回False。

例如：

如果满足以下条件，则返回True：
(s1, e1)= 8,10
(s2, e2) = 9, 11

(s1, e1)= 7,10
(s2, e2) = 8, 9

(s1, e1)= 8,11
(s2, e2) = 9, 11 以此类推

- sam_33

---

我看到许多特定于某种语言的问题（http://stackoverflow.com/search?q=overlapping+date+ranges），这些问题可能有一些有用的答案，但是没有一般性的东西... - jball

实际上，这看起来并不复杂 - 只需要几个 if 来判断日期是否重叠。如果按照某种方式（例如基于它们的开始时间，然后是结束时间）对日期进行排序，则可以简化和减少这些 if 的数量。 - pnt

这只是我之前在stackoverflow上回答的变体：https://dev59.com/KXVC5IYBdhLWcg3w7V1q#143568 - Lasse V. Karlsen

面试官可能想要看看你是如何解决这个问题的（我会像Lasse在他的链接答案中所做的那样画一张图）。 - Justin

可能是重复问题：http://stackoverflow.com/questions/4718004/tricky-interview-question - finnw

Answer 1

这是基本的区间代数，详见我的回答，代码看起来像这样：

bool IsConflict(Datetime s1, Datetime e1, Datetime s2, Datetime e2)
{
    return (s1 < e2) && (e1 > s2);
}

我假设两次会议，其中一次会议的开始时间在另一次会议结束时间之后，它们不会发生冲突。

- Lasse V. Karlsen

---

真遗憾这是社区维基，我认为你应该得到每个用户两个赞才对。 - jball

不，我明确将其设为 CW 以避免这种情况发生，问题在宽泛的条件下是重复的，但足够不同以独立存在，但我的答案不会，因此需要 CW。 - Lasse V. Karlsen

Answer 2

在两个区间的简单情况下，我认为这将起作用（未经测试的伪代码如下）：

bool IsConflict(Datatime s1, Datatime e1, Datatime s2, Datatime e2) {
    if( s1 < s2 ) {
        // meeting 1 starts first
        if( e1 > s2 ) return true; // overlap
    }
    else {
        // meeting 2 starts first
        if( e2 > s1 ) return true; // overlap
    }

    return false;
}

- Bill the Lizard

---

虽然我同意Lasse的解决方案更加优雅，但是在我看来你的解决方案更容易理解。 - Kristian

Answer 3

以下算法的复杂度为O(nlogn)

public boolean isConflicts(float startTime[], float endTime[])
{
    TreeMap<Float, Integer> map = new TreeMap<Float, Integer>();
    for (int i = 0; i < startTime.length; i++)
    {
        map.put(startTime[i], -1);
        map.put(endTime[i], 1);
    }

    Iterator<Integer>iter = map.values().iterator();
    while (iter.hasNext())
    {
        if ((iter.next() + iter.next()) != 0)
        {
             System.out.println ("Conflicts...");
             return true;
        }
    }
    return false;                 
}

- Nikhil K R

Answer 4

会议重叠当且仅当 max(s1, s2) < min(e1, e2)。基于这个交集的方法假定间隔 (s, e) 是开放的，并暗示（正确或错误）一个空 会议 s = e 不能与另一个会议重叠。

- antonakos

Answer 5

计划 这个问题有三种情况需要检查。

• 情况1：s1是否在区间[s2，e2]内（s1> = s2）&&（s1 <= e2）
• 情况2：e1是否在区间[s2，e2]内（e1> = s2）&&（e2<= e2）
• 情况3：点（s2，e2）是否在[s1，e1]内（s1<= s2）&&（e1>= e2）

所以这就是答案。我很抱歉；这不是最易读的代码行。

代码（伪代码）：

bool isConflict(Datetime s1, Datetime e1, Datetime s2, Datetime e2){
  return ((s1 >= s2) && (s1 <= e2)) || ((e1 >= s2) && (e2 <= e2)) || (s1 <= s2) && (e1 >= e2));
}

- Keith Holliday