Tasks

Merge Intervals

April 2023

Index	Name	Number	Difficulty	Link
1	Merge Intervals	56	Medium	https://leetcode.com/problems/merge-intervals/
2	Insert Interval	57	Medium	https://leetcode.com/problems/insert-interval/
3	Non-overlapping Intervals	435	Medium	https://leetcode.com/problems/non-overlapping-intervals/
4	Interval List Intersections	986	Medium	https://leetcode.com/problems/interval-list-intersections/
5	Meeting Rooms II	253	Medium	https://leetcode.com/problems/meeting-rooms-ii/
6	Maximum Number of Overlapping Intervals	1850	Medium	https://leetcode.com/problems/maximum-number-of-overlapping-intervals/
7	Remove Covered Intervals	1288	Medium	https://leetcode.com/problems/remove-covered-intervals/
8	Find Right Interval	436	Medium	https://leetcode.com/problems/find-right-interval/
9	Minimum Number of Arrows to Burst Balloons	452	Medium	https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
10	Employee Free Time	759	Hard	https://leetcode.com/problems/employee-free-time/

// 56. Merge Intervals

// Time: O(n log n) | Space: O(n)
var merge = function(intervals) {
    if (intervals.length < 2) {
        return intervals;
    }
    const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
    const res = [[...sorted[0]]];
    for (let i = 1; i < sorted.length; i++) {
        const last = res[res.length - 1];
        const curr = sorted[i];
        if (last[1] >= curr[0]) {
            last[1] = Math.max(last[1], curr[1]);
        } else {
            res.push([...curr]);
        }
    }
    return res;
};

/*
Merge Intervals
-------------------------------
1. Add first interval to the result.
2. Compare every [i] from intervals with the last in result.
3. Merge if they overlap. Push if do not overlap.
4. Return result.
-------------------------------
Time: O(n log n) | Space: O(n)
*/

// 57. Insert Interval

// Time: O(n) | Space: O(1)
var insert = function(intervals, newInterval) {
    if (!intervals.length) {
        return [newInterval];
    }
    let res = [[...intervals[0]]];
    let i = 1;
    // Push everything before the new one to the result.
    while (intervals[i]?.[0] < newInterval[0]) {
        res.push([...intervals[i]]);
        i++;
    }
    // If new one ends before the last one in the result.
    if (newInterval[1] < res[res.length - 1][0]) {
        res.unshift([...newInterval]);
    } 
    // If new one and last in the result intersects.
    else if (newInterval[0] <= res[res.length - 1][1]) {
        res[res.length - 1][0] = Math.min(res[res.length - 1][0], newInterval[0]);
        res[res.length - 1][1] = Math.max(res[res.length - 1][1], newInterval[1]);
    } 
    // If new one does not intersect with the last in the result.
    else {
        res.push([...newInterval]);
    }
    // Add the rest to the result.
    for (; i < intervals.length; i++) {
        const last = res[res.length - 1];
        const curr = intervals[i];
        if (last[1] >= curr[0]) {
            last[1] = Math.max(last[1], curr[1]);
        } else {
            res.push([...curr]);
        }
    }
    return res;
};

/*
Merge Intervals
--------------------------
1. Handle corner case.
2. Push to result all intevals before the new one.
3. Merge or push the new one.
4. Merge or push the rest.
5. Return result.
--------------------------
Time: O(n) | Space: O(1)
*/

// 435. Non-overlapping Intervals

// Time: O(n log(n)) | Space: O(1)
var eraseOverlapIntervals = function(intervals) {
    if (intervals.length < 2) {
        return 0;
    }
    intervals.sort((a, b) => a[0] - b[0]);
    let count = 0;
    let prevEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (prevEnd > intervals[i][0]) {
            count++;
            prevEnd = Math.min(prevEnd, intervals[i][1]);
        } else {
            prevEnd = intervals[i][1];
        }
    }
    
    return count;
};

/*
Intervals
-------------------------------
1. Handle corner cases.
2. Sort intervals in asc order.
3. Check if intervals overlaps -> n[0][1] (prevEnd) is greater than n[i][0] (nextStart). 
4.     Result++.
5.     Get the min end (interval with max end is deleted).
6. Return res.
-------------------------------
Time: O(n log(n)) | Space: O(1)
*/

// 986. Interval List Intersections

// Time: O(n) | Space: O(1)
var intervalIntersection = function(firstList, secondList) {
    const result = [];
    let i = 0;
    let j = 0;
    
    while (i < firstList.length && j < secondList.length) {
        let start = Math.max(firstList[i][0], secondList[j][0]);
        let end = Math.min(firstList[i][1], secondList[j][1]);
        if (end >= start) {
            result.push([start, end]);
        }
        if (end === firstList[i][1]) i++;
        if (end === secondList[j][1]) j++;
    }
    
    return result;
};

/*
Two Pointers
--------------------------
While (i < first.length && j < second.length)
    Start = Math.max(first[i][0], second[j][0]);
    End = Math.min(first[i][1], second[j][1]);
    If (end >= start) -> result.push([start, end]).
    Which end is used -> iterator++;
--------------------------
Time: O(n) | Space: O(1)
*/

// 253 Meeting Rooms II

// Time: O(n) | Space: O(n)
export function findSets(intervals) {
    if (intervals.length < 2) {
        return intervals.length;
    }
    const sortedIntervals = [...intervals].sort((a, b) => a.start - b.start);
    const minHeap = new MinHeap();
    minHeap.add(sortedIntervals[0].end);
    for (let i = 1; i < sortedIntervals.length; i++) {
        if (minHeap.peek() <= sortedIntervals[i].start) {
            minHeap.remove();
        }
        minHeap.add(sortedIntervals[i].end);
    }
    return minHeap.heap.length;
}