Meeting Conflict algorithms

Question

I had a interview today and was asked to check whether two meeting conflicts with each other or not. Each meeting has start time and end time. I tried to answer the question but not that specific..can somebody throw some idea?

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

should return true if Conflict is there and false if no conflict.

E.g

True if:
(s1, e1)= 8,10

(s2, e2) = 9, 11

(s1, e1)= 7,10

(s2, e2) = 8, 9

(s1, e1)= 8,11

(s2, e2) = 9, 11 and so on

I see [many language specific questions](http://stackoverflow.com/search?q=overlapping+date+ranges) that would have helpful answers, but nothing general... — jball, Feb 04 '11 at 20:05
There really is nothing more to it that it looks like - just a few `if`s to see whether the dates overlap. Those `if`s could be streamlined and reduced in number if, for example, dates are sorted in a certain way (for instance based on their start, and after that - on their end). — pnt, Feb 04 '11 at 20:08
This is just a variant of my answer here: http://stackoverflow.com/questions/143552/comparing-date-ranges/143568#143568 — Lasse V. Karlsen, Feb 04 '11 at 20:10
The interviewer probably wanted to see how you solved the problem (I would draw a picture like Lasse did in his linked answer) — Justin, Feb 04 '11 at 20:11
Possible duplicate: http://stackoverflow.com/questions/4718004/tricky-interview-question — finnw, Feb 04 '11 at 21:03

score 25 · Answer 1 · edited May 23 '17 at 11:46

25

This is basic interval algebra, see my answer here for more details, but the code would look like this:

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

I am assuming that two meetings where one start where the other ends are not in conflict.

edited May 23 '17 at 11:46

Community

1
1

answered Feb 04 '11 at 20:16

Lasse V. Karlsen

380,855
102
628
825

Too bad it's community wiki, I think you deserve two upvotes per user for that linked answer. – jball Feb 04 '11 at 20:22
2

No, I explicitly made it CW to avoid that, the question is in loose terms a duplicate, but enough different that it can stand on its own, but my answer would not be, hence CW. – Lasse V. Karlsen Feb 04 '11 at 20:25

score 2 · Answer 2 · answered Feb 04 '11 at 20:13

2

In the simple case of two intervals I think this will work (untested pseudocode ahead):

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

answered Feb 04 '11 at 20:13

Bill the Lizard

398,270
210
566
880

While I agree Lasse's solution is more elegant, your solution is more easily understood IMHO – Kristian Sep 20 '15 at 03:03

antonakos · Answer 3 · 2011-02-05T14:08:54.947

1

The meetings overlap if and only if max(s1, s2) < min(e1, e2). This intersection based approach assumes that intervals (s, e) are open, and implies (rightly or wrongly) that an empty meeting s = e cannot have an overlap with another meeting.

edited Feb 05 '11 at 14:08

answered Feb 04 '11 at 20:13

antonakos

8,261
2
31
34

score 1 · Answer 4 · edited Dec 06 '11 at 02:23

Complexity of following algorithm is 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;                 
}

score 0 · Answer 5 · answered Dec 12 '13 at 04:41

The plan There are three cases to check for with this problem.

Case 1: Does s1 lie within the interval [s2,e2] (s1 >= s2) && (s1 <= e2)
Case 2: Does e1 lie within the interval [s2, e2] (e1 >= s2) && (e2 <= e2))
Case 3: Does the point (s2, e2) lie within [s1, e1] (s1 <= s2) && (e1 >= e2)

So here is the answer. I apologize; It's not the most readable lines of code.

The code (pseudo):

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

Meeting Conflict algorithms

5 Answers5