Алгоритм нахождения максимального количества непересекающихся действий, которые может выполнить один или несколько человек в Javascript - PullRequest
Новая
       109

Алгоритм нахождения максимального количества непересекающихся действий, которые может выполнить один или несколько человек в Javascript

0 голосов
/ 06 марта 2020

У меня есть эта проблема:

Вам дано n действий с их началом и окончанием sh раз. Выведите максимальное количество действий, которое может выполнять один или несколько человек, предполагая, что человек может одновременно работать только над одним действием. Конечное sh время действия может быть равно времени начала следующего.

Что является вариацией этого: https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

предлагаемое здесь решение https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/ завершается неудачей на test_2b. Предлагаемое здесь решение https://www.youtube.com/watch?v=i_G8hZYcKnI в 2:55 завершается неудачей на test_1a.

Я пытаюсь найти алгоритм, который бы быстро работал и для больших чисел. 

const test_1a = {
    availablePeople: 1,
    tasks: [
        { start: 1, end: 2 },
        { start: 4, end: 5 },
        { start: 6, end: 7 },
        { start: 3, end: 8 }
    ]
}
const test_1b = {
    availablePeople: 2,
    tasks: [
        { start: 1, end: 2 },
        { start: 4, end: 5 },
        { start: 6, end: 7 },
        { start: 3, end: 8 }
    ]
}
const test_2a = {
    availablePeople: 1,
    tasks: [
        { start: 1, end: 4 },
        { start: 2, end: 6 },
        { start: 7, end: 9 },
        { start: 5, end: 10 }
    ]
}
const test_2b = {
    availablePeople: 2,
    tasks: [
        { start: 1, end: 4 },
        { start: 2, end: 6 },
        { start: 7, end: 9 },
        { start: 5, end: 10 }
    ]
}

const solution_1 = ({ availablePeople, tasks }) => {
    tasks.sort((a, b) => a.end - b.end);
    for (let i = 0; i < availablePeople; i++) {
        let previousEnd = 0;
        for (let i = 0; i < tasks.length; i++) {
            const task = tasks[i];
            if (!task.confirmed && task.start >= previousEnd) {
                task.confirmed = true
                previousEnd = task.end
            }
        }
    }
    const confirmedTasks = tasks.filter(task => task.confirmed);
    return confirmedTasks.length
}

const solution_2 = ({ availablePeople, tasks }) => {
    tasks.sort((a, b) => a.start - b.start)
    const neededPeople = [];
    let task;
    for (let i = 0; i < tasks.length; i++) {
        task = tasks[i];
        let foundPerson;
        let person;
        for (let i = 0; i < neededPeople.length; i++) {
            person = neededPeople[i];
            if (person.availableStart <= task.start) {
                foundPerson = person;
                break;
            }
        }
        if (!foundPerson) {
            const newPerson = {
                availableStart: task.end,
                numberOfTasks: 1
            }
            neededPeople.push(newPerson);
        } else {
            foundPerson.availableStart = task.end;
            foundPerson.numberOfTasks = foundPerson.numberOfTasks + 1;
        }
    }
    neededPeople.sort((a, b) => b.numberOfTasks - a.numberOfTasks);
    let maxNumOfTasks = 0;
    for (let i = 0; i < neededPeople.length; i++) {
        if (i === availablePeople) break;
        maxNumOfTasks += neededPeople[i].numberOfTasks;
    }
    return maxNumOfTasks;
}

console.log(solution_1(test_1a)) // should output 3
console.log(solution_1(test_1b)) // should output 4
console.log(solution_1(test_2a)) // should output 2
console.log(solution_1(test_2b)) // should output 4 - instead outputs 3

console.log(solution_2(test_1a)) // should output 3 - instead outputs 2
console.log(solution_2(test_1b)) // should output 4
console.log(solution_2(test_2a)) // should output 2
console.log(solution_2(test_2b)) // should output 4
...