Javascript-форум (https://javascript.ru/forum/)
-   Элементы интерфейса (https://javascript.ru/forum/dom-window/)
-   -   Как правильно решить задачу про диапазоны часов? (https://javascript.ru/forum/dom-window/82858-kak-pravilno-reshit-zadachu-pro-diapazony-chasov.html)

dc65k 19.07.2021 16:31

Как правильно решить задачу про диапазоны часов?
 
Всем привет. Недавно увидел задачу, написал небольшое решение. Подскажите, как более правильно её решить?
Дан список отсутствий работников на рабочем месте, например [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));

ksa 19.07.2021 17:15

Цитата:

Сообщение от dc65k
Требуется вывести диапазоны часов, когда все работники были на местах. Рабочий день: 9-18 ч

Ищи максимальное "снизу" и минимальное "сверху"...

ksa 19.07.2021 17:19

dc65k, текста у тебя дофига... Все в одном цикле можно сделать.

рони 19.07.2021 18:30

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>

Vlasenko Fedor 20.07.2021 01:17

<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:

Alexandroppolus 20.07.2021 05:55

Цитата:

Сообщение от Vlasenko Fedor
Вариант

Если не ошибаюсь, можно идти от старта, тогда не придется сортировать второй раз
<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>

Vlasenko Fedor 20.07.2021 08:42

Alexandroppolus,

4.2.2. Составление расписания стр 61
Олимпиадное программирование. / пер. с англ. А. А. Слинкин – М.:
ДМК Пресс, 2018. – 300 с.: ил.
ISBN 978-5-97060-644-5

идея – отсортировать события по времени конца и выбирать в
качестве следующего событие, которое заканчивается как можно раньше.
Оказывается, что этот алгоритм всегда дает оптимальное решение.

Alexandroppolus,
твой вариант лучше, не увидел коллизий, в этом примере


Часовой пояс GMT +3, время: 13:27.