- Описание
- Отправленные решения
179. Робот для пулл-реквестов
В компании X есть своя система контроля версий. Эта VCS не умеет анализировать изменения в файлах и может смёржить два реквеста автоматически, если они не содержат изменений в одних и тех же файлах.
В определённый момент запускается робот, который автоматически мёржит в мастер пулл-реквесты. Задача робота — смёржить наибольшее количество изменений, после чего дежурный разработчик собирает текущий мастер в релиз и отдаёт его в тестирование.
Робот принимает на вход список реквестов, отсортированных по времени создания. В данных о каждом реквесте содержится список файлов, которые в нём изменились, и время создания реквеста. В каждом реквесте может быть изменён хотя бы один файл.
Робот должен вернуть массив с идентификаторами реквестов в том порядке, в котором их нужно смёржить. При этом робот должен влить максимум изменений (количество изменённых файлов) без конфликтов в порядке времени создания реквестов.
Напишите код этого робота.
Формат ввода
На вход подаётся массив реквестов. Длина массива - не более 1000, количество конфликтующих между собой пулл-реквестов заранее не известно.
У каждого реквеста такая структура:
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) {
// ваш код
}Примечание
Ваше решение не должно использовать внешних зависимостей.
Примеры входных и выходных данных
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(',')
);Ограничения
Ограничение времени
4 с
Ограничение памяти
64 МБ