JavaScript Solutions, Competitive programming in JavaScript, MCQ in JS

Monday, 19 December 2022

A solution to LeetCode Problem 56. Merge Intervals in JavaScript


A solution to LeetCode Problem 56. Merge Intervals in JavaScript 

In this problem, we are given an array of intervals, where each interval is an object with a start and end property. The intervals are not necessarily sorted. Our task is to merge any overlapping intervals and return the resulting array of intervals.

Problem Statement:

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.


Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.



  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104


To solve this problem, you can use a greedy approach, where you first sort the intervals based on the start time, and then you can merge the overlapping intervals one by one. Here is a JavaScript solution that demonstrates this approach:

function merge(intervals) {
  if (!intervals.length) return intervals;

  // sort intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);

  // initialize the merged intervals with the first interval
  let merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    let currentInterval = intervals[i];
    let lastMergedInterval = merged[merged.length - 1];

    // if the current interval overlaps with the last merged interval, merge them
    if (currentInterval[0] <= lastMergedInterval[1]) {
      lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
    } else {
      // otherwise, add the current interval to the merged intervals

  return merged;

This solution has a time complexity of O(n * log(n)), since the intervals are sorted using the built-in Array.sort() function, which has a time complexity of O(n * log(n)). The space complexity is O(n), since we create a new array to store the merged intervals.

I hope this helps! Let me know if you have any questions or suggestions for improvement.

No comments:

Post a Comment