Яндекс Блиц Фронт 2: Финал #6

Продолжаем серию задач из конкурса от Яндекса

«Робот для пулл-реквестов»

В компании X есть своя система контроля версий. Эта VCS не умеет анализировать изменения в файлах и может смёржить два реквеста автоматически, если они не содержат изменений в одних и тех же файлах.

В определённый момент запускается робот, который автоматически мёржит в мастер пулл-реквесты. Задача робота — смёржить наибольшее количество изменений, после чего дежурный разработчик собирает текущий мастер в релиз и отдаёт его в тестирование.

Робот принимает на вход список реквестов, отсортированных по времени создания. В данных о каждом реквесте содержится список файлов, которые в нём изменились, и время создания реквеста. В каждом реквесте может быть изменён хотя бы один файл.

Робот должен вернуть массив с идентификаторами реквестов в том порядке, в котором их нужно смёржить. При этом робот должен влить максимум изменений (количество изменённых файлов) без конфликтов в порядке времени создания реквестов.

Напишите код этого робота.

Формат ввода

На вход подаётся массив реквестов. Длина массива - не более 1000, количество конфликутющих между собой пулл-реквестов - не более 20.

У каждого реквеста такая структура:

type PullRequest = { 
    /** 
     * Массив имён изменённых файлов (отсортирован лексикографически) 
     * Длина массива N: 1 <= N <= 1000 
     */ 
    files: string[], 
    /** 
     * Уникальный идентификатор реквеста в VCS 
     */ 
    id: string, 
    /** 
     * Unix-timestamp создания пулл-реквеста 
     */ 
    created: number, 
}

Время создания (created) и идентификатор (id) каждого реквеста – уникальны.

Формат вывода

Код робота должен экспортироваться в виде CommonJS-модуля вида:

/** 
 * @param {PullRequest[]} pullRequests массив PR, отсортированных по времени создания 
 * @returns {string[]} идентификаторы реквестов в порядке мёржа 
 */ 
module.exports = function (pullRequests) { 
    // ваш код 
}

Примечания

Ваше решение будет тестироваться в NodeJS версии v9.11.2.

Оно не должно использовать внешних зависимостей.

Примеры входных и выходных данных

function mergeAllPRs(prs) { /* solution */ } 
console.assert( 
    mergeAllPRs([ 
        { 
            id: ’#1’, 
            created: 1536077100, 
            files: [’.gitignore’, ’README.md’] 
        }, 
        { 
            id: ’#2’, 
            created: 1536077700, 
            files: [’index.js’, ’package-lock.json’, ’package.json’] 
        }, 
        { 
            id: ’#3’, 
            created: 1536077800, 
            files: [’.pnp.js’, ’yarn.lock’] 
        } 
    ]) 
    .join(’,’) === [ 
        "#1", 
        "#2", 
        "#3" 
    ].join(’,’) 
); 
console.assert( 
    mergeAllPRs([ 
        { 
            id: ’#1’, 
            created: 1536074100, 
            files: [’README.md’] 
        }, 
        { 
            id: ’#2’, 
            created: 1536078700, 
            files: [’README.md’] 
        }, 
        { 
            id: ’#3’, 
            created: 1536097800, 
            files: [’README.md’] 
        } 
    ]).join(’,’) === [ 
        "#1" 
    ].join(’,’) 
); 
console.assert( 
    mergeAllPRs([ 
        { 
            id: ’#1’, 
            created: 1536077100, 
            files: [’.gitignore’, ’README.md’] 
        }, 
        { 
            id: ’#2’, 
            created: 1536077700, 
            files: [’index.js’, ’package-lock.json’, ’package.json’] 
        }, 
        { 
            id: ’#3’, 
            created: 1536077800, 
            files: [’.pnp.js’, ’package-lock.json’, ’yarn.lock’] 
        }, 
        { 
            id: ’#4’, 
            created: 1536077900, 
            files: [’index.spec.js’, ’index.spec.ts’, ’index.ts’] 
        } 
    ]) 
    .join(’,’) === [ 
        "#1", 
        "#2", 
        "#4" 
    ].join(’,’) 
);