Алгоритмы встречных конфликтов

Question

Сегодня у меня было интервью, и меня попросили проверить, конфликтуют ли две встречи друг с другом или нет. У каждой встречи есть время начала и окончания. Я пытался ответить на вопрос, но не на что-то конкретное. Кто-нибудь может что-нибудь подсказать?

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

должно возвращать true, если конфликт существует, и false, если нет конфликта.

Например,

True, если:
(s1, e1) = 8,10

(s2, e2) = 9, 11

(с1, е1) = 7,10

(s2, e2) = 8, 9

(с1, е1) = 8,11

(s2, e2) = 9, 11 и так далее

Answer 1

Это базовая алгебра интервалов, см. мой ответ здесь для более подробной информации , но код будет выглядеть так:

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

Я предполагаю, что две встречи, одна из которых начинается там, где заканчивается другая, не конфликтуют.

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;
}

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;                 
}

Answer 4

Встречи перекрываются, если и только если max(s1, s2) < min(e1, e2).Этот подход, основанный на пересечении, предполагает, что интервалы (s, e) открыты, и подразумевает (правильно или ошибочно), что пустое собрание s = e не может перекрываться с другим совещанием.

Answer 5

План Есть три случая, чтобы проверить с этой проблемой.

• Случай 1: лежит ли s1 в интервале [s2, e2] (s1> = s2) && (s1 <= e2) </li>
• Случай 2: лежит ли e1 в интервале [s2, e2] (e1> = s2) && (e2 <= e2)) </li>
• Случай 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));
}