3 ms·

This is close but you need to ensure the start time is before the other ends, and test for the second one starting before the first also. There's four cases: [

by aldarn 9y ago

This is close but you need to ensure the start time is before the other ends, and test for the second one starting before the first also. There's four cases: [appointment 1 start] [1 end] <-- some time --> [appointment 2 start] [2 end] (case 1 - no overlap, appointment 1 first) [appointment 1 start] [appointment 2 start] <-- some time --> [1 end] [2 end] (case 2 - overlap, appointment 1 first) [appointment 2 start] [appointment 1 start] <-- some time --> [2 end] [1 end] (case 3 - overlap, appointment 2 first) [appointment 2 start] [2 end] <-- some time --> [appointment 1 start] [1 end] (case 4 - no overlap, appointment 2 first) So you need to do: if (appointment1.end > appointment2.start AND appointment1.start < appointment2.end) OR (appointment2.end > appointment1.start AND appointment2.start < appointment1.end) // conflict

kornish 9y ago
> if appointment1.end > appointment2.start OR appointment2.end > appointment1.start // conflict This actually isn't correct. Consider the events (0, 3) and (4, 6). The end of the second (6) comes after the beginning of the first (0), but they don't conflict. You want `and`, not `or`. EDIT: oops, just saw you edited it. Good catch :)
jon_richards 9y ago
Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite, but your pseudocode still covers those cases.
- aldarn 9y ago
  True, I didn't include those cases as they are not unique in terms of why there is / isn't a conflict. But you're right, worth including for completion.
- tzs 9y ago
  > Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite [...] Your notation there, where instead of a pair of start/end pairs you have a list of tagged times, reminds me of a good approach if one is doing a generalized version of the problem: given a list of N appointments, find conflicts. Make a list of tagged times, where a tagged time is a triplet (time, 1, name) if appointment named "name" starts at time "time", and is (time, -1, name) if appointment named "name" ends at "time". Sort the tagged time list with time ascending as the primary sort key, and the start/stop tag ascending as the secondary key. Now to find conflicts you simply scan through the tagged times list, keeping a running total of the start/end tag values. If the running total is greater than 0 when you begin to process a given entry, that entry has a conflict with an earlier appointment, and the running total is how many earlier appointments it conflicts with. As described above, this lets you print a list of what appointments have conflicts with earlier appointments, but it doesn't give an easy way to say which earlier appointments conflict. If you want to do that, it is straightforward. Just add a set data structure, and during the scan of tagged times add "name" to the set when you encounter an appointment's start, and remove "name" when you encounter an appointment's end. When you find a conflict, the set contains the names of all of the earlier appointments the present appointment conflicts with. The above assumed that two appointments do not conflict if the ending time of the first is the same as the starting time of the second. If that should be counted as a conflict, just change the sort so that the secondary key is sorted descending instead of ascending.
flukus 9y ago
Does anyone really test for specifics like this? I thought the goal was to ensure the candidate understood that dates and times are abstract numbers, anyone that applies a mathematical operator should pass it. Yes this would still filter out a lot of people.
codingdave 9y ago
Or just sort by start time, then do the simple check.
- s_kilk 9y ago
  Yeah, this is way easy if the two events are sorted by start_time first.
Stratoscope 9y ago
I was thinking along the same lines as you, but it turns out you only need two comparisons and one logical operator. barrkel has a thorough explanation here: https://news.ycombinator.com/item?id=14641485 https://news.ycombinator.com/item?id=14641485 Or, as I realized later, it seems helpful to me if I look at it as a practical problem instead of an abstract one: https://news.ycombinator.com/item?id=14642059 https://news.ycombinator.com/item?id=14642059
Flenser 9y ago
a = Appointment 1 start A = Appointment 1 end b = Appointment 2 start B = Appointment 2 end The only predicates are: a < A, b < B The complete set of orderings are thus: aAbB - no overlap bBaA - no overlap abAB - partial overlap baBA - partial overlap abBA - complete overlap of one appointment inside the other baAB - complete overlap of one appointment inside the other

by aldarn 9y ago

kornish 9y ago

> if appointment1.end > appointment2.start OR appointment2.end > appointment1.start // conflict This actually isn't correct. Consider the events (0, 3) and (4, 6). The end of the second (6) comes after the beginning of the first (0), but they don't conflict. You want `and`, not `or`. EDIT: oops, just saw you edited it. Good catch :)

jon_richards 9y ago

Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite, but your pseudocode still covers those cases.

aldarn 9y ago
True, I didn't include those cases as they are not unique in terms of why there is / isn't a conflict. But you're right, worth including for completion.
tzs 9y ago
> Your cases don't consider [1 start][2 start][2 end][1 end] or the opposite [...] Your notation there, where instead of a pair of start/end pairs you have a list of tagged times, reminds me of a good approach if one is doing a generalized version of the problem: given a list of N appointments, find conflicts. Make a list of tagged times, where a tagged time is a triplet (time, 1, name) if appointment named "name" starts at time "time", and is (time, -1, name) if appointment named "name" ends at "time". Sort the tagged time list with time ascending as the primary sort key, and the start/stop tag ascending as the secondary key. Now to find conflicts you simply scan through the tagged times list, keeping a running total of the start/end tag values. If the running total is greater than 0 when you begin to process a given entry, that entry has a conflict with an earlier appointment, and the running total is how many earlier appointments it conflicts with. As described above, this lets you print a list of what appointments have conflicts with earlier appointments, but it doesn't give an easy way to say which earlier appointments conflict. If you want to do that, it is straightforward. Just add a set data structure, and during the scan of tagged times add "name" to the set when you encounter an appointment's start, and remove "name" when you encounter an appointment's end. When you find a conflict, the set contains the names of all of the earlier appointments the present appointment conflicts with. The above assumed that two appointments do not conflict if the ending time of the first is the same as the starting time of the second. If that should be counted as a conflict, just change the sort so that the secondary key is sorted descending instead of ascending.

flukus 9y ago

Does anyone really test for specifics like this? I thought the goal was to ensure the candidate understood that dates and times are abstract numbers, anyone that applies a mathematical operator should pass it. Yes this would still filter out a lot of people.

codingdave 9y ago

Or just sort by start time, then do the simple check.

s_kilk 9y ago
Yeah, this is way easy if the two events are sorted by start_time first.

Stratoscope 9y ago

I was thinking along the same lines as you, but it turns out you only need two comparisons and one logical operator. barrkel has a thorough explanation here: https://news.ycombinator.com/item?id=14641485 https://news.ycombinator.com/item?id=14641485 Or, as I realized later, it seems helpful to me if I look at it as a practical problem instead of an abstract one: https://news.ycombinator.com/item?id=14642059 https://news.ycombinator.com/item?id=14642059

Flenser 9y ago

a = Appointment 1 start A = Appointment 1 end b = Appointment 2 start B = Appointment 2 end The only predicates are: a < A, b < B The complete set of orderings are thus: aAbB - no overlap bBaA - no overlap abAB - partial overlap baBA - partial overlap abBA - complete overlap of one appointment inside the other baAB - complete overlap of one appointment inside the other