Posted in the Operation Spark #daily-progammer Slack
You are trying to schedule all day meetings with certain groups of coworkers. Everyone at the company email you days they will be unavailable. So you have a list that looks like this:
| Name | From | To |
|---|---|---|
| Jason | 2020-06-10 | 2020-06-13 |
| Kaley | 2020-05-29 | 2020-06-12 |
| Ted | 2020-06-15 | 2020-06-15 |
| Leigh | 2020-05-29 | 2020-06-03 |
| Leigh | 2020-06-19 | 2020-06-23 |
| Jason | 2020-05-25 | 2020-06-01 |
| Jonah | 2020-06-15 | 2020-06-20 |
| Leigh | 2020-06-22 | 2020-06-27 |
Dates are inclusive (so 2020-06-10 through 2020-06-11 means the person will be out for two days)
Write a function that will take a list of names who must be present for the meeting, and the earliest date the meeting could possibly happen on, and returns the earliest all of those people could meet.
So first thing first, we would start by filtering down the list to only the people we care about. That’s easy. Also, to do anything beyond simply checking each date against every date range, we are going to have to sort the ranges. Probably by start date is most useful, but there’s probably some better indexing scheme available. I’m just going to keep it simple for now.
So lets imagine we have a layout of blocked off day ranges as follows
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| | | | | | | | | | | | | |
| | | | | | +D------+------+------+ | | +H-----+
| | | | | | +-------+------+------+ | | +------+
| | | | | | | | | | | | | |
|+A-----+-------+------+------+ | | | | | | | | |
|+------+-------+------+------+ | | | | | | | | |
| | | | | | | | | | | | | |
| +B------+------+ | | +E------+ | | | | | |
| +-------+------+ | | +-------+ | | | | | |
| | | | | | | | | | | | | |
| | +C-----+------+------+------+ | | | +G-----+ | |
| | +------+------+------+------+ | | | +------+ | |
| | | | | | | | | | | | | |
| | | | | | +F------+------+------+ | | | |
| | | | | | +-------+------+------+ | | | |
- So if we start with date range
Awe know we cannot possibly have a day free till5. - But hold on, we can’t just think about day
5, we need to track every date range that starts before then:B, C. Taking the max date range blocks us out through day6 - We now examine the next date range to start to see if it starts more than one day after.
Dstarts on day7so the answer is no - We re-start the process, we are now blocked out through the max end date of
D, E, Fwhich is9 - The range that starts after
9starts on day11. Day11must be our solution!
An important bit we are leaving out in the above is how to start on a given day. For example if our earliest day was 4 then we should start with all ranges which have a start date before, and an end date on or after (A, C in consideration)
| Name | From | To |
|---|---|---|
| Alex | 2020-01-01 | 2020-01-04 |
| Bill | 2020-01-02 | 2020-01-03 |
| Carol | 2020-01-03 | 2020-01-06 |
| Dan | 2020-01-07 | 2020-01-09 |
| Bill | 2020-01-07 | 2020-01-07 |
| Fran | 2020-01-07 | 2020-01-09 |
| Dan | 2020-01-13 | 2020-01-13 |
| Carol | 2020-01-11 | 2020-01-11 |
const addDay = isoDate => {
const d = new Date(isoDate)
d.setDate(d.getDate()+1)
return d.toISOString().split(`T`)[0]
}
const getNextAvailableDay = (startingAt, blackoutRanges) => {
const it = blackoutRanges[Symbol.iterator]()
let nextProspectiveDate = startingAt
let nextRange = null
while(true) {
nextRange = it.next()
if(nextRange.done)
return nextProspectiveDate
if(nextRange.value.from > nextProspectiveDate)
break
if(nextRange.value.to >= nextProspectiveDate)
nextProspectiveDate = addDay(nextRange.value.to)
}
return nextProspectiveDate
}<<getNextAvailableDay>>
const blackoutRanges = input.map(([person, from, to]) => ({person, from, to})).sort((a, b) => a.from < b.from ? -1 : 1)
return getNextAvailableDay("2020-01-01", blackoutRanges)2020-01-10
Aaand…wait…I think that just solved it, did it not? Uhh…lets try this out
<<getNextAvailableDay>>
const blackoutRanges = input.map(([person, from, to]) => ({person, from, to})).sort((a, b) => a.from < b.from ? -1 : 1)
const testData = [
//earliest expected //sliceRanges
["2020-01-01", "2020-01-10", 0],
["2020-01-07", "2020-01-10", 0],
["2020-01-10", "2020-01-10", 0],
["2020-01-11", "2020-01-12", 0],
["2020-01-13", "2020-01-14", 0],
["2020-01-18", "2020-01-18", 0],
["2020-01-18", "2020-01-18", 100],
]
return [
["Earliest", "Slice", "Expected", "Calculated"],
...testData.map(([earliest, expected, sliceRanges]) =>
[earliest, sliceRanges, expected, getNextAvailableDay(earliest, blackoutRanges.slice(sliceRanges))])
]| Earliest | Slice | Expected | Calculated |
| 2020-01-01 | 0 | 2020-01-10 | 2020-01-10 |
| 2020-01-07 | 0 | 2020-01-10 | 2020-01-10 |
| 2020-01-10 | 0 | 2020-01-10 | 2020-01-10 |
| 2020-01-11 | 0 | 2020-01-12 | 2020-01-12 |
| 2020-01-13 | 0 | 2020-01-14 | 2020-01-14 |
| 2020-01-18 | 0 | 2020-01-18 | 2020-01-18 |
| 2020-01-18 | 100 | 2020-01-18 | 2020-01-18 |
Those all match up with expected values…cool
Ok, the last step is just to add the names filtering and try it on the original data
So here we have
<<getNextAvailableDay>>
const getNextAvailableDayForPeople = (startingAt, names, blackoutRanges) => (
getNextAvailableDay(
startingAt,
blackoutRanges.filter(x => names.includes(x.person)).sort((a, b) => a.from < b.from ? -1 : 1)
)
)And testing that against the original example we get our answers
<<getNextAvailableDayForPeople>>
const blackoutRanges = originalExample.map(([person, from, to]) => ({person, from, to}))
return [
["Jason", "Kaley", "Ted"],
["Fran", "Jason", "Leigh"],
["Jonah", "Jason"],
["Jason"],
["Jason", "Kaley", "Leigh", "Ted", "Jonah"],
].map(names => [names.join(), getNextAvailableDayForPeople("2020-05-25", names, blackoutRanges)])| Jason,Kaley,Ted | 2020-06-14 |
| Fran,Jason,Leigh | 2020-06-04 |
| Jonah,Jason | 2020-06-02 |
| Jason | 2020-06-02 |
| Jason,Kaley,Leigh,Ted,Jonah | 2020-06-14 |