Merge intervals - task from JS interview | Solving LeetCode problems

[@evgeniychip]

Очень хорошо объяснил и разжевал, спасибо, надеюсь канал продолжит жить

[@SerzhNesteruk]

Спасибо за задачу! И я тоже подумал о сортировке. Отсортировал даже сами интервалы. Код получился, правда, немного избыточен. Вот моё решение: function merge(intervals) { intervals.forEach(arr => arr.sort((a, b) => a - b)); intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]); const result = []; let prev = intervals[0]; for (let curr of intervals) { if (prev[0] === curr[0] && prev[1] === curr[1]) continue; if (prev[1] >= curr[0]) { prev[1] = Math.max(prev[1],curr[1]); } else { result.push(prev); prev = curr; } } result.push(prev); return result; }

[@abolnikov]

Красиво. Для подготовки к собеседованию очень полезно

[@brothers_karamazovs]

Спасибо! Вроде бы простая задачка, а закодить за время интервью оптимальный вариант оказалось непросто))

[@almazyakhin7246]

Очень хорошо объяснил и разжевал, спасибо, надеюсь канал продолжит жить(copy) Коммент для поддержки, спасибо за видео, добрый человек

[@artisswis5058]

Интересная задачка🙂 function mergeInterval(intervals) { const sortIntervals = intervals.sort((a,b) => a[0]-b[0]) return sortIntervals.reduce((acc, [start, end]) => { if(acc.length === 0){ acc[0] = [start,end] return acc } const lastIndexAcc = acc.length - 1; const nextIndexAcc = acc.length; const endLastInterval = acc[lastIndexAcc][1]; const startLastInterval = acc[lastIndexAcc][0]; endLastInterval >= start ? acc[lastIndexAcc] = [startLastInterval, end] : acc[nextIndexAcc] = [start,end]; return acc }, []) }

[@frontendscience]

Благодарю за решение! Вышло отлично!

[@Сергей-у6и7б]

Ох уж этот литкод) Эта задача легкая и интуитивно понятная, а порой встретишь медиум и голову над ней часами ломаешь

[@frontendscience]

:) ну это очень индивидуально. Но здорово, что для Вас это уже легкая задача!

[@valeriakan6474]

Задачка класс, спасибо Сергей, что делитесь опытом! Правда сначала делала без сортировки, а когда увидела 3-й кейс пришлось добавить (конечно на ум сразу он пришел, но хотелось верить, что входной массив будет уже отсортирован). Радует что мой велосипед похож с вашим) const mergeIntervals = (arr) => { arr.sort((a,b) => a[0] - b[0]) const mergeArr = []; for (let i = 0; i < arr.length; i++) { let end = arr[i][1]; while (arr[i+1] && (end >= arr[i+1][0])) { end = (end > arr[i+1][1]) ? end : arr[i+1][1]; i++; } mergeArr.push([arr[i][0], end]) } return mergeArr; }

[@frontendscience]

Отлично вышло! Благодарю за решение!

[@akitmentorconsultant4696]

3 раза встречал эту задачу в реальных приложениях: календари, расписания, рабочие смены и т.д. ещё у этой задачи есть частный случай: Например, когда интервалы кольцевые то интервал с 23:00 до 6:00.

[@frontendscience]

да очень практическая задача!

[@antonio7446]

С кольцевыми кажется ещё сложнее

[@akitmentorconsultant4696]

@@antonio7446 скажите если потребуется подсказка

[@dandanq958]

Очень тяжело даются такие задачи....спасибо за видео

[@frontendscience]

Придет с практикой! Эта задача миддл и синьер уровень.

[@alexmanwell]

@@frontendscience это реально задача уровня middle or senior уровня? Она же простая. Не зря я решал год задачи на codewars и немного на других ресурсах. Кстати, мое решение: const merge = (intervals) => { intervals = intervals.sort((a, b) => a[0] - b[0]); let result = []; while (intervals.length) { let [current, next] = [intervals[0], intervals[1]]; if (next && next[0] next[1]) { next = current; } else { next = [current[0], next[1]]; } intervals[1] = next; intervals.shift(); } else { result.push(current); intervals.shift(); } } return result; };

[@anatoliymonaka4435]

@@alexmanwell где вы получили базу? Подскажете?

[@alexmanwell]

@@anatoliymonaka4435 Анатолий, толком то я и не получал базы целенаправленно. Я изначально знал несколько структур данных и алгоритмов. Структуры данных я читал в книге Шилдта и Брюс Эккель про java (Colletction Framework). А про алгоритмы Седжвика "Алгоритмы на java" ( у него прикольно показаны алгоритмы сортировки в ООП стиле). Сейчас в основном смотрю на youtube: Oleksandr Tsymbaliuk и еще несколько других каналов посвященных алгоритмам, без лекций 2 часовых. Из полезных советов, то на codewars в разделе practice в левом сайдбаре сортировать задачи по наиболее решенным (most completed). и выбирать уровень kata, желательно начиная не выше 6. 7 уровень никак не научит решать алгоритмические задачи. Там каждые 150 -200 задач из 6 kata сложность задач вырастает. Это вы будете ощущать. С какого то момента задачи 6 kata (это если что легкий уровень) будут такие же или сложнее, чем middle задачи c leetcode. На leetcode можно тоже решать задачи начиная с уровня easy. Чтоб хоть как-то научиться решать задачи на алгоритмы, то на это нужно потратить много времени. То есть типа научиться за 50 - 100 часов не прокатит. Более реально за 300 - 500 часов решения задач. И да это будет по хорошему решение уровня middle на leetcode и 5, 4 kata на codewars. Как-то так. Если есть какие-то вопросы уточняющие, пишите, отвечу.

[@alexmanwell]

@@anatoliymonaka4435 Анатолий, толком то я и не получал базы целенаправленно. Я изначально знал несколько структур данных и алгоритмов. Структуры данных я читал в книге Шилдта и Брюс Эккель про java (Colletction Framework). А про алгоритмы Седжвика "Алгоритмы на java" ( у него прикольно показаны алгоритмы сортировки в ООП стиле). Сейчас в основном смотрю на youtube: Oleksandr Tsymbaliuk и еще несколько других каналов посвященных алгоритмам, без лекций 2 часовых. Из полезных советов, то на codewars в разделе practice в левом сайдбаре сортировать задачи по наиболее решенным (most completed). и выбирать уровень kata, желательно начиная не выше 6. 7 уровень никак не научит решать алгоритмические задачи. Там каждые 150 -200 задач из 6 kata сложность задач вырастает. Это вы будете ощущать. С какого то момента задачи 6 kata (это если что легкий уровень) будут такие же или сложнее, чем middle задачи c leetcode. На leetcode можно тоже решать задачи начиная с уровня easy. Чтоб хоть как-то научиться решать задачи на алгоритмы, то на это нужно потратить много времени. То есть типа научиться за 50 - 100 часов не прокатит. Более реально за 300 - 500 часов решения задач. И да это будет по хорошему решение уровня middle на leetcode и 5, 4 kata на codewars. Как-то так. Если есть какие-то вопросы уточняющие, пишите, отвечу.

[@blgarOk]

Спасибо, интересная задачка. Мое решение: function merge(intervals) { intervals.sort((a,b) => a[0] - b[0]) for (let i = 0; i < intervals.length; i++) { if(intervals[i + 1] && intervals[i][1] >= intervals[i + 1][0]) { const start = intervals[i][0] const end = intervals[i + 1][1] intervals.splice(i, 2, [start, end]) i-- } } return intervals }

[@frontendscience]

Отлично вышло - благодарю за решение!

[@frontendscience]

@@johnnyrocketkite4738 а я думаю, тебе пора с канала! Бля, ВОЙНА идет, а ты мне херню пишешь!

[@mikhaildevichensky6407]

вы лучший !

[@frontendscience]

Благодарю за поддержку! Того же мнения о нашей аудитории :)

[@alex_osx]

спасибо за контент=) function merge(intervals) { intervals.sort((left, right) => left[0] - right[0]); const result = [intervals.splice(0, 1)[0]]; for (let interval of intervals) { if (result.at(-1)[1] >= interval[0]) { result.at(-1)[1] = Math.max(result.at(-1)[1], interval[1]); } else { result.push(interval); } } return result; }

[@alex_osx]

досмотрел видео - решение получилось идентичное) правда, за сложность не совсем понял - почему не линейная?

[@frontendscience]

Отличное решение! Сложность не линейная из-за sort. Сложность самой сортировки n*log n.

[@alex_osx]

@@frontendscience благодарю =)

[@kulyasan1522]

В новом синтаксисе у прототипа Array есть такой метод at, с помощью его можно в меньшее кол-во символов получить доступ к последнему элементу массива. Спасибо за видео))

[@frontendscience]

Да есть такой. Но он еще слишком "свежий". Поэтому в видео использовал "проверенный долгими годами практики" способ

[@whiteguards43]

А можно решение через этот метод?

[@colnbluth-bx8nt]

Все больше убеждаюсь, насколько полезен codewars

[@ProoksiusSvaagali]

Единственное лишнее действие в этом алгоритме - мы в начале сравниваем самый первый элемент, который сразу поместили в result, с самим собой. Можно его вытащить из intervals с пом. shift. Не скопировать в result, а переместить.

[@ВладПашковский-ц2э]

Могу ошибаться, но лишняя итерация по циклу с присвоением значения будет дешевле шифта, который из начала массива достаёт элемент и под капотом все индексы других элементов переписывает у массива. С таким примером этого не видно, но если их будет 10 000, то ощутится.

[@alexmanwell]

@@ВладПашковский-ц2э Так оно и есть дешевле.

[@vadavur]

Добрый день! Спасибо за контент) Вышло такое решение - так нормально делать в бою или лучше разбить код, используя промежуточные переменные для сортировки и редьюса, а в конце, соответственно, return [переменная]? И точно ли нужно делать проверку на передачу пустого/одноинтервального массива? По идее в большинстве случаев должны приходить многоинтервальные, и эта проверка чаще всего будет напрасной, а если придет-таки пустой/одноинтервальный, то и он отработается. function merge(intervals) { return intervals.sort((a,b) => a[0] - b[0]).reduce((mergedArr, interval) => { const lastInterval = mergedArr[mergedArr.length - 1]; if (lastInterval[1] >= interval[0]) { lastInterval[1] = Math.max(lastInterval[1], interval[1]); } else { mergedArr.push(interval); } return mergedArr; }, [intervals[0]]); }

[@frontendscience]

Благодарю за решение! Отличный вариант вышел. На счет кода в бою - сложно сказать. Тут каждый решает руководствуясь собственным чувством прекрасного ) Я лично за большее количество переменных - в угоду читаемости кода. По поводу проверки на пустой или одноитнервальный массив - то тут нужна проверка на один интервал. Так как по условию задачи 1

[@vadavur]

@@frontendscience Спасибо за ответ! Похоже, прорешивание задач на codewars с последующим сравнением своих решений с чужими побочно прививает плохую практику пытаться уместить все в одной цепочке)

[@dardawill7253]

Сергей, здравствуйте. Надеюсь, вы в порядке. Очень нравится ваша подача материала, с удовольствием смотрю канал. У меня есть вопрос касательно одного непонятного мне момента в данном решении. Надеюсь, если у вас будет возможность, вы сможете прояснить. В строке кода recent[1] = Math.max(recent[1], interval[1]), как после этой строки сразу изменяется значение нашего result? Т.е было [1 2], а после max, стало [1 5]. Заранее спасибо

[@clenbuterol4989]

так он серый гей слился после фейка про донецк и 8 лет

[@konstantin6837]

Если еще актуально, то массив - ссылочный тип данных

[@dardawill7253]

@@konstantin6837 спасибо

[@astkh4381]

Где лучше решать code wars или leetcode

[@AzamatAbduvohidov99]

👍

[@dev_margooo]

Я решила следующим образом: 1. Смапила исходные ноды таким образом, чтобы было понятно, какая из них является началом интервала, а какая концом 2. Отсортировала полученные ноды 3. Проитерировалась по ним. Завела переменную start для хранения старта текущего интервала и count для количества отрезков, которые вошли в текущий. 3.1. Если нода была типа start: 3.1.1. Если у меня еще не было начатого интервала (start = undefined), то начинала новый интервал и увеличивала счетчик отрезков на 1 3.1.2. Если начатый интервал уже был, то тогда увеличивала счетчик на 1. 3.2. Если нода типа end, тогда уменьшала счетчик на 1. Далее, если счетчик после этого оказывался равен 0, значит, все вошедшие отрезки закончились, можно завершать интервал. Брала value текущей ноды, это и был конец интервала. Старт был известен, так что складывала полученный интервал в массив результатов. Если счетчик не был равен 0, то переходила к следующей итерации. function merge(arg) { const map = mapNodes(arg); const sortedMap = sortNodes(map); const result = []; let start; let count = 0; for(let i=0; i

[@bogdanbasarab1621]

здравствуйте , а сколько вы занимаетесь программированием ? заранее спасибо за ответ ;)

[@yarik83men51]

Вы супер. Жду ка Хатико Ваши уроки

[@frontendscience]

😄 Очень рады видеть наших преданных подписчиков!

[@fizzbuzz5807]

Спасибо! Часто на собеседованиях попадаются задачи такой сложности? Легко решаю leetcode easy и некоторые leetcode medium. Эту сам не решил.

[@stanislavw9709]

исходя из опыта собеседований на джуна/мидла - ни разу (был примерно на 10 сбесах и в основном на мидла). Обычно дают что-то совсем легкое (типа примитивной рекурсии).

[@frontendscience]

Очень зависит от компании. В Яндексе вполне могут и такую дать. В прошлом году у коллеги спрашивал - говорит, что они easy и medium дают на разогрев. Классно, что Вы решаете задачи на литкоде - очень полезно! Успехов!

[@fizzbuzz5807]

@@frontendscience большое спасибо!

[@semen_1991]

Здравствуйте, Сергей. У меня один вопрос по поводу подсчета сложности данного алгоритма. Почему n * logN ? ведь for of бежит так же по всему массиву, тобишь получается тоже N а не logN. Помогите плиз разобратся, заранее спасибо!

[@olgasoloma]

Я так понимаю, сложность сортировки O(n * log n), а у цикла O(n). В итоге сложность решения этой задачи O(n * log n + n). А дальше по правилу "Если в O есть сумма, нас интересует самое быстрорастущее слагаемое. Это называется асимптотической оценкой сложности" n откидывается и остается O(n * log n).

[@opticsandspectrometry994]

здесь правильнее называть "отрезки", а не "интервалы", поскольку в интервал не входят крайние точки, а 2й пример показывает, что стыковка всё-таки включает точку стыковки. Еще такой вопрос, а почему Вы уверены, что a[0]

[@EvilYou]

Смог решить за O(n). Вместо того, чтобы сортировать исходный массив я воспользовался свойством числовых ключей объекта (они расположены от меньшего к большему). function merge(intervals) { let obj = {}; for (let i = 0; i < intervals.length; i++) { let [start, end] = intervals[i]; if (!(start in obj) || obj[start] < end) { obj[start] = end; } } let sorted = Object.entries(obj).map( ([a, b]) => [+a, b] ); let result = []; let last = sorted[0][1]; for (let i = 0; i < sorted.length; i++) { let current = sorted[i]; if (i === 0) { result.push(current); continue; } let [start, end] = current; if (end last) { result.push(current); } else { result[result.length - 1][1] = end; } last = end; } return result; }; Результат на leetcode: Runtime 93ms Beats 94.83%

[@EvilYou]

@@flatstorycentury То есть, по-вашему, метод Object.entries выполняет сортировку?

[@EvilYou]

@@flatstorycentury числовые индексы, как вы и написали, записываются в объект уже отсортированными (сначала положительные, затем отрицательные, затем уже нечисловые идут). Операция записи свойства в объект занимает O(1). Object.entries не сортирует, а лишь преобразует объект в массив, как есть. Можно с таким же успехом заменить Object.entries на цикл for (let key in obj). Сложность цикла, как мы знаем, O(n). Выглядит и правда странно, что мой алгоритм, якобы, сортирует быстрее, чем быстрая сортировка, которая выполняется за O(n * log n). Но тут, на мой взгляд, дело в том, что запись свойств с числовым ключом в объект будет занимать не константное время, а логарифмическое O(log n), так как при записи числового свойства (а они все числовые) в объект происходит переупорядочивание элементов (неявный бинарный поиск). В таком случае вложенная в цикл логарифмическая сложность и даст O(n * log n) по итогу.

[@EvilYou]

​@@flatstorycentury где я такое написал? Прочитайте внимательно еще раз мой комментарий. Я имею ввиду, что заявленная мной изначально O(n) де факто быстрее O(n * log n). А O(n * log n) - сложность сортировки. Далее, я пришел к тому же выводу, что и вы насчет скорости работы алгоритма, просто это было не вполне очевидно.

[@EvilYou]

@@flatstorycentury Если вывести объект в консоль, мы заметим, что числовые индексы в нем уже отсортированы. Но операция записи свойства в объект является константной по сложности. Исходя из этих двух противоречивых высказываний делаем вывод, что сложность все же не O(1), так как сортировка не может быть бесплатной операцией. Но она происходит не после записи свойств в объект, так как это заняло бы O(n * log n), а во время записи свойств в объект, используя бинарный поиск (или что-то аналогичное). Конечно, это все мои умозаключения, как на деле это все устроено - неизвестно :)

[@EvilYou]

@@flatstorycentury да, именно это я и написал в конце одного из комментариев: "В таком случае вложенная в цикл логарифмическая сложность и даст O(n * log n) по итогу.". Вообще, интересная дискуссия получилась. Я раньше думал об операции записи свойства в объект как об операции сложностью O(1). Но, выходит, это не всегда так. Поэтому быстрая сортировка была бы, в данном случае, короче и проще.

[@natalyabublikova3344]

Каждый раз пушить и потом патчить последнее значение - это очень по-фронтэндерски. О каких логарифмах, омикронах и сложностях алгоритма мы говорим, если нет никакой оптимизации? Какие-то громкие слова про расходы памяти и прочее. короче мой говнокод, который по крайней мере в массив пишет реже и ничего не патчит. Да и читать кажется легче. let begin = mas[0][0] let end = mas[0][1] for (let i = 1; i < mas.length; i++) { let t = mas[i] if(end < t[0]){ masNew.push([begin, end]) begin = t[0] end = t[1] } else { end = Math.max(t[1], end) } } masNew.push([begin, end]) return masNew

[@stasbelov4954]

"Дорого" обходится сортировка. function merge(list){ list.sort((a, b) =>{ return a[0]-b[0] }) let out = [] list.forEach(([start,end])=>{ let last = out.pop() if(!last){ out.push([start,end]) }else{ let [last_s, last_e] = last if(start

[@frontendscience]

Да сортировка не из дешевых! Благодарю за решение -отлично вышло!

[@netamgdenado]

А разве в input3 результат не должен быть [1,12]?, там же пересечение [[1,4] ->,, { let result = []; arr.sort((a,b) => a[0] - b[0]) result.push(arr[0]) arr.forEach((item, index) => { if(index !== 0) { const lastItem = result[result.length - 1][1] const isMerged = lastItem - item[0] === 1 || lastItem - item[0] === -1 || lastItem - item[0] === 0 if(isMerged) { result[result.length - 1][1] = item[1] } else if(!(result[result.length - 1][1] > item[0])) { result.push(item) } } }) return result; }

[@PEDRO-rs6ei]

Не очень читабельно но кажется работает получилось в 17 строк изучаю js только 20 дней. Подскажите пожалуйста это правильное решение? function merge (arr) { arr.sort((a, b) => { return a[0] - b[0]; }); for(let i = 1; i < arr.length; i++) { if(arr[i-1][1] >= arr[i][0]) { arr[i-1][0] = arr[i-1][0] arr[i-1][1] = arr[i][1] arr.splice(i, 1); } } console.log(arr); }

[@ЯрославГоловко-ф6и]

Вроде работает правильно. function merge(array) { const begin = 0; const end = array.length - 1; // checking all intervals for (let i = begin; i < array.length; ++i) { // checking elems in intervals for (let j = begin; j < i; ++j) { // if first number of interval entering if (j !== i && (array[j][0] = array[i][0])) { let tmp = [...array[i], ...array[j]]; array[i] = [Math.min(...tmp), Math.max(...tmp)]; array[j] = []; } // if second number of interval entering else if (j !== i && (array[j][0] = array[i][1])) { let tmp = [...array[i], ...array[j]]; array[j] = [Math.min(...tmp), Math.max(...tmp)]; array[i] = []; } } } let array_copy = []; // clearing rubbish for (const i of array) { if (i.length > 0) { array_copy.push(i); } } return array_copy; }

[@frontendscience]

Благодарю за решение!

[@ДашаКороткевич]

А если имеется в виду просто промежуток, а не интервал? те первое число может быть больше второго? А все не продуман алгоритм! Всегда лучше уточнять все

[@denchik421-d7b]

Получилось выполнить без сортировки, то есть мой алгоритм не сортирует данные const array1 = [[3, 19], [1, 11]]; const merge = (array) => { let status = false; let result = []; for (let i = 0; i < array.length; i++) { if (result.length != 0) { for (let a = 0; a < result.length; a++) { // проверяем на дубликат if (result[a][0] == array[i][0] && result[a][1] == array[i][1]) { status = true; } // если один интервал полностью входит в другой else if (result[a][0] = array[i][1]) { status = true; } else if (array[i][0] = result[a][1]) { result[a] = array[i]; status = true; } // если один интервал неполностью пересекает другой else if (array[i][0] >= result[a][0] && array[i][0] = array[i][0] && result[a][0]

[@frontendscience]

Благодарю за решение. Сложность правда будет квадратичной в этом случае.

[@MemoresCode]

let result = [] for(let i = 0;i=two[0]){ result.push(one[0],two[1]) } } } return result

[@GreenGotty]

Спасибо за задачу! Тоже думал про sort и reduce, но потянуло на мапинг.. xD var merge = function (intervals) { if (intervals.length < 2) return intervals; let map = Object.create(null); for (let i = 0; i < intervals.length; i++) { const int = intervals[i]; const intStart = int[0]; const intEnd = int[int.length - 1]; if (intStart === intEnd) { if (map[intStart] === undefined) { map[intStart] = 'same'; } continue; } if (map[intStart] !== 'mid') { map[intStart] = map[intStart] === 'end' ? 'mid' : 'start'; } for (let z = intStart + 1; z < intEnd; z++) { map[z] = 'mid'; } if (map[intEnd] !== 'mid') { map[intEnd] = map[intEnd] === 'start' ? 'mid' : 'end'; } } const keys = Object.keys(map); let res = []; let start = +keys[0]; keys.forEach((key) => { switch (map[key]) { case 'same': res.push([+key, +key]); break; case 'start': start = +key; break; case 'end': res.push([start, +key]); break; default: end = +key; } }); if (!res.length) res.push([start, end]); return res; };

[@frontendscience]

Благодарю за решение ) прикольно получилось с маппингом

[@jonsnow8488]

Мое решение немного громоздкое не все же) const mergeIntervals = (intervals) => { const mergedIntervals = [] let startPoint = 0 let endPoint = 0 let nextStartPoint = 0 let nextEndPoint = 0 let shouldGoNext = true intervals.sort((a, b) => a[0] - b[0]) for (let i = 0; i < intervals.length; i++) { if (shouldGoNext) { startPoint = intervals[i][0] endPoint = intervals[i][1] } nextStartPoint = i+1 < intervals.length && intervals[i+1][0] nextEndPoint = i+1 < intervals.length && intervals[i+1][1] if (nextStartPoint && endPoint >= nextStartPoint) { shouldGoNext = false if (endPoint < nextEndPoint) { endPoint = nextEndPoint } } else { shouldGoNext = true mergedIntervals.push([startPoint, endPoint]) } } return mergedIntervals }

[@alexgolubev1182]

const intrv1 = [ [8, 10], [1, 3], [15, 18], [2, 6], ]; const intrv2 = [ [1, 4], [4, 5], ]; const mergeIntervals = (intervals) => { let result = intervals.sort((a,b) => a[0] > b[0] ? 1 : -1); for (let i = 0; i < result.length - 1; i++) { const currentInterval = result[i]; const nextInterval = result[i + 1]; if (currentInterval[1] >= nextInterval[0]) { const start = Math.min(...currentInterval, ...nextInterval); const end = Math.max(...currentInterval, ...nextInterval); result[i] = [start, end]; result.splice(i+1, 1); i--; } } return result; }; console.log(mergeIntervals(intrv1)); // [[1, 6], [8, 10], [15, 18]] console.log(mergeIntervals(intrv2)); // [[1, 5]]

[@frontendscience]

Отлично вышло! Благодарю, что поделились решением!

[@ЭрэсТриггеров]

function merge(arr) { arr.sort((a,b) => a[0] - b[0]); let result = [arr[0]]; for (let i = 1; i < arr.length; i++){ if (result[result.length - 1][1] >= arr[i][0]){ if (result[result.length - 1][1] < arr[i][1]){ result[result.length - 1][1] = arr[i][1]; } }else result.push(arr[i]); } return result; }

[@DraginAnatoliy]

насчет сложности по памяти немного не понял)

[@frontendscience]

нативный метод sort использует память - ему понадобится log n памяти для сортировки. Но мы не делали копию исходно массива. Если сделать копию и потом сортировать то сложность по памяти выйдет линейная.

[@ВладиславДребот]

function merge(input) { const sortedInput = input.sort((a, b) => a[0] - b[0]) const output = sortedInput.reduce((acc, item) => { const lastIndex = acc.length - 1 const accLast = acc[lastIndex] if (lastIndex >= 0 && item[0]

[@frontendscience]

Благодарю за решение! Отлично вышло!

[@alexandroppolus]

return [...acc, item] всё портит. Лучше заменить на acc.push(item); return acc;

[@kotyaboko]

function merge(arr) { if (arr.length < 2) { return arr; } arr.sort((a, b) => a[0] - b[0]); let res = []; arr.map((item, index) => { if (index == 0) { res.push(item); return; } if (item[0]

[@kotyaboko]

можна було б також для останнього елемента результату зробити зміну було б більш читабельно та швидше напевно

[@pasha.serhiichuk]

// my solution function mergeIntervals(array) { if (array.length a[0] - b[0]) const result = [array[0]] let resultIndex = 0 for (let i = 0; i < array.length; i++) { let item1 = array[i] if (item1[0] > result[resultIndex][1] && item1[1] > result[resultIndex][1]) { result.push(item1) resultIndex += 1 } else { result[resultIndex][1] = item1[1] } } return result } якось працює))

[@СтасМайоров]

/* function intervals(arr) { let sortArr = arr.sort((a, b) => a[0] - b[0]); let newArr = []; if (Math.max(...sortArr[0]) > Math.min(...sortArr[1])) { newArr.push([Math.min(...sortArr[0]), Math.max(...sortArr[1])]); sortArr.splice(0, 2); } else { newArr.push(sortArr[0], sortArr[1]); sortArr.splice(0, 2); } if (sortArr.length === 0) { return newArr; } else { return newArr.concat(intervals(sortArr)); } }

[@ЕвгенийТрофимов-я6т]

const checkIntervals = ([,a], [b]) => b [a[0], Math.max(...a, ...b)]; const merge = intervals => intervals .sort(([a], [b]) => a - b) .reduce((acc, value) => { const findedInterval = acc.find((interval) => checkIntervals(interval, value)) return [ ...acc.filter(interval => interval !== findedInterval), mergeInterval(value, findedInterval), ]; }, []);

[@djdfrkfcbr5402]

function marge(intervals){ const interval = intervals.sort((a, b) => a[0] - b[0]); let newArr =[interval[0]]; interval.map((item,index)=>{ if(index>0){ if(newArr[newArr.length-1][1] >= item[0]){ newArr[newArr.length-1][1] = item[1]; newArr[newArr.length-1][0] = Math.min( newArr[newArr.length-1][0],item[0]); } else{ newArr.push(item); }}}) return newArr; }

[@frontendscience]

Отлично! Благодарю за решение!

[@whiteguards43]

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums) { if(nums.length < 2){ return nums } const res = [] const sorting = nums.sort((a, b) => a[0] - b[0]) for(let i = 0; i < sorting.length; i++){ if(i < sorting.length - 1){ if(sorting[i][1] >= sorting[i+1][0]){ res.push([sorting[i][0], sorting[i + 1][1]]) }else{ res.push(sorting[i]) } } } return res }; console.log(topKFrequent([[1,3], [2,6], [8, 10], [15, 18]])) console.log(topKFrequent([[1,4], [4,5]])) на название не обращаем внимание

[@sergeik1245]

круто, спасибо вам * * * function merge(inputData) { inputData.sort((a, b) => a[0] - b[0]); let x3 = []; for (let i = 0; i < inputData.length; i++) { x3.length === 0 || x3[x3.length - 1][1] < inputData[i][0] ? x3.push(inputData[i]) : (x3[x3.length - 1][1] = inputData[i][1]); } return x3; }