Как правильно решить задачу про диапазоны часов?
Всем привет. Недавно увидел задачу, написал небольшое решение. Подскажите, как более правильно её решить?
Дан список отсутствий работников на рабочем месте, например [9,10] - с 9:00 до 10:00 Требуется вывести диапазоны часов, когда все работники были на местах. Рабочий день: 9-18 ч input: [ [9, 10], [15, 17], [14, 16], ] output: [ [10, 14], [17, 18], ] Моё решение: /* input: [ [9, 10], [15, 17], [14, 16], ] output: [ [10, 14], [17, 18], ] */ const input = [ [9, 10], // 10 - 18 [15, 17], // 9 - 15 // 17 - 18 [14, 16], // 9 - 14 // 16 - 18 ]; const getWorkTime = (input) => { const obj = {}; for (let i = 9; i <= 18; i++) { obj[i] = 0; } for (const value of input) { obj[value[0]] += 1; obj[value[1]] += 1; } let isNegative = false; let item = []; const keys = Object.keys(obj); const output = keys.reduce((accumulator, currentValue, index, array) => { if (obj[currentValue] === 0) { isNegative = true; if (isNegative) { item.push(currentValue); } } else { isNegative = false; } if (!isNegative && item.length) { accumulator.push(item); item = []; } if (index === keys.length - 1) { accumulator.push(item); } return accumulator; }, []); return output.map((currentValue) => { return [Number(currentValue[0]) - 1, Number(currentValue[output.length]) + 1]; }).map((currentValue) => { if (!currentValue[1]) { currentValue[1] = currentValue[0] + 1; } return currentValue; }); } console.log(getWorkTime(input)); |
Цитата:
|
dc65k, текста у тебя дофига... Все в одном цикле можно сделать.
|
dc65k,
<script> /* input: [ [9, 10], [15, 17], [14, 16], ] output: [ [10, 14], [17, 18], ] */ const input = [ [9, 10], [15, 17], [14, 16] ]; const getWorkTime = (input, min, max) => { let ar = [], temp = [], push; for (let i = min; i <= max; i++) { let clear = input.some(([a, b]) => i >= a && i < b); let len = temp.length; if (clear) { if (len) { temp[1] = i; temp = []; push = false; } } else temp[+!!len] = i; if (temp.length == 2 && !push) { ar.push(temp); push = true; } } return ar } let a = getWorkTime(input, 9, 18); document.write(JSON.stringify(a)) </script> |
<script> const res = []; const workTime = [9, 18]; const input = [ [9, 10], [15, 17], [14, 16], ]; let [start, end] = workTime; input.sort((a, b) => b[1] - a[1]).forEach(([a, b]) => { if (b < end) res.push([b, end]); end = Math.min(a, end); }); if (end > start) res.push([start, end]); document.write(JSON.stringify(res.sort(([a], [b]) => a - b))); </script> Вариант :dance: |
Цитата:
<script> const res = []; const workTime = [9, 18]; const input = [ [9, 10], [15, 17], [14, 17.4], ]; let [start, end] = workTime; input.sort(([a], [b]) => a - b).forEach(([a, b]) => { if (start < a) res.push([start, a]); start = Math.max(start, b); }); if (start < end) res.push([start, end]); document.write(JSON.stringify(res)); </script> |
Alexandroppolus,
4.2.2. Составление расписания стр 61 Олимпиадное программирование. / пер. с англ. А. А. Слинкин – М.: ДМК Пресс, 2018. – 300 с.: ил. ISBN 978-5-97060-644-5 идея – отсортировать события по времени конца и выбирать в качестве следующего событие, которое заканчивается как можно раньше. Оказывается, что этот алгоритм всегда дает оптимальное решение. Alexandroppolus, твой вариант лучше, не увидел коллизий, в этом примере |
Часовой пояс GMT +3, время: 07:46. |