Interval coding pattern

Interval overlapping

Given two intervals (a and b), there will be six different ways the two intervals can relate to each other:

Let’s solve few problems related to intervals.

Many intervals problem can also be solved by Sweep line technique. Refer following blogs for more details.

Sweep line algorithm on intervals related problems

56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

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].

Approach #1: Build graph and merge intervals using connected components

1. We can represent each interval as a graph node.
2. Between each pair of intervals, if they overlap then we can add undirected edge between them.
3. Run connected components algorithm and merge it with single interval.
4. To merge connected component, we can use start=min(interval) and end=max(interval) .
5. Time complexity: O(n*n)

Following is code for reference.

const dfs = (graph, node, visited) => {
    visited.add(node);
    let [min, max] = node;
    for (const neighbor of graph.get(node)) {
        if (!visited.has(neighbor)) {
            const [localMin, localMax] = dfs(graph, neighbor, visited);
            min = Math.min(min, localMin);
            max = Math.max(max, localMax);
        }
    }
    return [min, max];
}
const isOverlap = (u, v) => {
    if(u[0] > v[0]) {
        return isOverlap(v,u);
    }
    if (u[1] < v[0]) {
        return false;
    }
    return true;
}
const buildGraph = intervals => {
    const graph = new Map();
    const n = intervals.length;
    for (let i = 0; i < n; i++) {
        const u = intervals[i];
        if (!graph.has(u)) {
            graph.set(u, []);
        }
        for (let j = i + 1; j < n; j++) {
            const v = intervals[j];
            if (!graph.has(v)) {
                graph.set(v, []);
            }
            if (isOverlap(u, v)) {
                graph.get(u).push(v);
                graph.get(v).push(u);
            }
        }
    }
    return graph;
}
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
    const graph = buildGraph(intervals);
    const visited = new Set();
    const ans = [];
    for (const interval of intervals) {
        if (!visited.has(interval)) {
            const merged = dfs(graph, interval, visited);
            ans.push(merged);
        }
    }
    return ans;
};

Approach #2: Sort intervals and the merge the neighbors

If we sort the intervals by their start value, then each set of intervals that can be merged will appear as a contiguous "run" in the sorted list. Time complexity O(nlogn).

In case of overlap, we will manually keep merging it. Following is code for reference.

class Solution {
private:
    static bool compare(vector<int> a, vector<int> b) { return a[0] < b[0]; }
    bool isOverlap(vector<int>& a, vector<int>& b) {
        if (a[0] > b[0]) {
            return isOverlap(b, a);
        }
        if (a[1] < b[0]) {
            return false;
        }
        return true;
    }
    void merge(vector<int> &a, vector<int> &b) {
        a[0] = min(a[0], b[0]);
        a[1] = max(a[1], b[1]);
    }

public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<vector<int>> ans;
        ans.push_back(intervals[0]);
        int n = intervals.size();
        for (int i = 1; i < n; i++) {
            vector<int>& a = ans[ans.size() - 1];
            vector<int>& b = intervals[i];
            if (isOverlap(a, b)) {
                merge(a, b);
            } else {
                ans.push_back(b);
            }
        }
        return ans;
    }
};

57. Insert Interval

https://leetcode.com/problems/insert-interval/description/

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don’t need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Approach: Linear Search

1. We can do a linear search by iterating through all the intervals to find out position to insert new interval.
2. Insert intervals which are less than the new interval.
3. Merge new interval with the rest of intervals if any
4. Copy the rest of the intervals.

Following is code for reference.

class Solution {
private:
    bool isOverlap(vector<int> a, vector<int> b) {
        if (a[0] > b[0]) {
            return isOverlap(b, a);
        }
        if (a[1] < b[0]) {
            return false;
        }
        return true;
    }
    void merge(vector<int>& a, vector<int>& b) {
        a[0] = min(a[0], b[0]);
        a[1] = max(a[1], b[1]);
    }

public:
    vector<vector<int>> insert(vector<vector<int>>& intervals,
                               vector<int>& newInterval) {
        vector<vector<int>> ans;
        int n = intervals.size();
        int i = 0;
        // skip all intervlas to find place to insert
        while (i < n &&  intervals[i][1] < newInterval[0]) {
            ans.push_back(intervals[i]);
            i++;
        }

        // Keep merging rest with interval if any
        while (i < n && isOverlap(newInterval, intervals[i])) {
            merge(newInterval, intervals[i]);
            i++;
        }
        // insert merged new interval
        ans.push_back(newInterval);

        // Copy rest
        while (i < n) {
            ans.push_back(intervals[i]);
            i++;
        }
        return ans;
    }
};

986. Interval List Intersections

https://leetcode.com/problems/interval-list-intersections/description/

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Approach #1: Use merge sort merging approach

Similar to merge two sorted array we can apply merging. Following is code for reference.

class Solution {
private:
    bool isOverlap(vector<int> a, vector<int> b) {
        if (a[0] > b[0]) {
            return isOverlap(b, a);
        }
        if (a[1] < b[0]) {
            return false;
        }
        return true;
    }
    vector<int> findIntersection(vector<int> a, vector<int> b) {
        int start = max(a[0], b[0]);
        int end = min(a[1], b[1]);
        return {start, end};
    }

public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int i = 0, j = 0;
        int m = firstList.size(), n = secondList.size();
        vector<vector<int>> ans;
        while (i < m && j < n) {
            // If overlap, get intersection
            if (isOverlap(firstList[i], secondList[j])) {
                vector<int> intersection =
                    findIntersection(firstList[i], secondList[j]);
                ans.push_back(intersection);
            }
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};

Interval List union

Given two sorted, non-overlapping interval lists, return a 3rd interval list that is the union of the input interval lists.

Sorted non-overlapping interval list: an array of intervals that don’t overlap with each other and are sorted by interval start.

Example # 1

Input: list1# {[1,2], [3,9]}, list2# {[4,6], [8,10], [11,12]}
Output# {[1,2], [3,10], [11,12]}

Approach # Apply merge sort merge phase approach

We can’t simply apply the intersection approach as per the previous problem. Since we need to keep merging the possible overlap therefore we need to take different approach here as below.

1. Use i and j as two pointer for first and second list.
2. First process the smallest starting interval and increment the corresponding pointer.
3. During processing, check if last interval of answer needs to be merged or not.

Following is code for reference.

class Solution {
private:
    bool isOverlap(vector<int> a, vector<int> b) {
        if (a[0] > b[0]) {
            return isOverlap(b, a);
        }
        if (a[1] < b[0]) {
            return false;
        }
        return true;
    }
    void merge(vector<int>& a, vector<int>& b) {
        a[0] = min(a[0], b[0]);
        a[1] = max(a[1], b[1]);
    }
    void process(vector<vector<int>>& ans, vector<int>& interval) {
        if (ans.size() == 0) {
            ans.push_back(interval);
        } else {
            vector<int>& c = ans[ans.size() - 1];
            if (isOverlap(c, interval)) {
                merge(c, interval);
            } else {
                ans.push_back(interval);
            }
        }
    }

public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int i = 0, j = 0;
        int m = firstList.size(), n = secondList.size();
        vector<vector<int>> ans;
        while (i < m && j < n) {
            vector<int> first = firstList[i];
            vector<int> second = secondList[j];
            if (first[0] < second[0]) {
                process(ans, first);
                i++;
            } else {
                process(ans, second);
                j++;
            }
        }
        // Copy rest
        while (i < m) {
            process(ans, firstList[i++]);
        }
        while (j < n) {
            process(ans, secondList[j++]);
        }
        return ans;
    }
};

435. Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals/description/

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Approach #1: Use overlap detection approach

1. We sort by the first element in the intervals
2. When we encounter an overlap, we increase the count, and decide to remove the interval with the larger end time.
3. In code, this translates to setting the “prevEnd” (the end time of the most recent non-deleted interval) to Math.min(current interval that we have encountered the conflict with, current prevEnd).

Following is code for reference.

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let prevEnd = intervals[0][1];
    let ans = 0;
    for (let i = 1; i < intervals.length; i++) {
        // If overlap with previous interval
        if (prevEnd > intervals[i][0]) {
            ans++;
            prevEnd = Math.min(prevEnd, intervals[i][1]);
        } else {
            prevEnd = intervals[i][1];
        }
    }
    return ans;
};

Approach #2: Use dynamic programming

First we need to sort intervals based on end so that we can apply the comparison to find out the if overlapping or not.

We can come up with following recursion relations

f(i, prev) = return minimum number of intervals removed to make overall non operlap
f(i, prev) = for each i, we have to choice, either choose or remove
           = min(
              f(i+1, i) ,  // choose, only if not overlapping
              f(i+1,prev)
              ) 

Following is code for reference.

const recursion = (intervals, prev, i, cache) => {
    const n = intervals.length;
    // base case: end of the intervals
    if (i === n) {
        return 0;
    }
    const key = i;
    if (cache.has(key)) {
        return cache.get(key);
    }
    let choose = Number.MAX_SAFE_INTEGER;

    // Choice: choose current only if not overlapping
    if (prev === -1 || intervals[prev][1] <= intervals[i][0]) {
        choose = recursion(intervals, i, i + 1, cache);
    }

    // Choice: remove current interval
    const remove = 1 + recursion(intervals, prev, i + 1, cache);

    const result = Math.min(choose, remove);
    cache.set(key, result);
    return result;
}
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    // sort intervals based on end time
    intervals.sort((a, b) => a[1] - b[1])
    return recursion(intervals, -1, 0, new Map())
};

759. Employee Free Time

https://leetcode.com/problems/employee-free-time/description/

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Approach

1. We can apply sweep line algo find all places where there are no intervals.
2. Create list of events [time, flag] flag = 0 mean start , flag = 1 mean end.
3. Track balance, if flag=0 then balance++ otherwise balance--
4. List our regions where balance = 0

Following is code for reference.

/**
 * // Definition for an Interval.
 * function Interval(start, end) {
 *    this.start = start;
 *    this.end = end;
 * };
 */

/**
 * @param {Interval[][]} schedule
 * @return {Interval[]}
 */
var employeeFreeTime = function(schedule) {
    const events = [];
    for (const employee of schedule) {
        for (const {start, end} of employee) {
            events.push([start, 0]);
            events.push([end, 1]);            
        }
    }
    // sort all events
    events.sort((a, b) => {
        // ascending order if time is different
        if(a[0] !== b[0]) {
            return a[0] - b[0];
        }
        // if same then keep start in the beginning
        return a[1] - b[1];
    });
    const output = [];
    let balance = 0;
    // sweep each timeline
    for (let i=0; i < events.length; i++) {
        const  [time, flag] = events[i];
        
        // check for answer
        if(balance === 0 && i > 0) {
            output.push(new Interval(events[i-1][0], time ));
        }
        // if start then increment
        if(flag === 0) {
            balance++;
        } else {
            // decrement
            balance--;
        }        
    }
    return output;
};

Line segment overlapping

A line segment can also be treated as interval as below if height of line is same.

If height of line segment is same then we can easily apply the interval based overlapping technique.

836. Rectangle Overlap

https://leetcode.com/problems/rectangle-overlap/description/

To find the x overlap, let’s think about the projection made by the corners of the rectangles on the x-axis and use the line segment technique to find out the overlap.

We can see that these points create two line segments — one formed by (ax1,0),(ax2,0), and the other one formed by (bx1,0),(bx2,0).

Now, finding x overlap is equivalent to finding the intersection of these two line segments.

We can apply same interval approach to find out overlap and write code as below.

class Solution {
    bool isLineSegmentOverlapped(int x1, int x2, int x3, int x4) {
        if (x1 > x3) {
            return isLineSegmentOverlapped(x3, x4, x1, x2);
        }
        if (x2 <= x3) {
            return false;
        }
        return true;
    }

public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        auto [x1, y1, x2, y2] = tie(rec1[0], rec1[1], rec1[2], rec1[3]);
        auto [x3, y3, x4, y4] = tie(rec2[0], rec2[1], rec2[2], rec2[3]);
        return isLineSegmentOverlapped(x1, x2, x3, x4) &&
               isLineSegmentOverlapped(y1, y2, y3, y4);
    }
};

223. Rectangle Area

https://leetcode.com/problems/rectangle-area/description/

Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).

Example 1:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

Approach # Find the overlap area

If two rectangle doesn’t overlap then total area will be sum of both rectangles. Otherwise we need to subtract the area for overlapped region.

Following is code for reference.

class Solution {
private:
    int area(int x1, int y1, int x2, int y2) { return (x2 - x1) * (y2 - y1); }
    bool lineSegmentOverlap(int x1, int x2, int x3, int x4) {
        if (x1 > x3) {
            return lineSegmentOverlap(x3, x4, x1, x2);
        }
        if (x2 <= x3) {
            return false;
        }
        return true;
    }
    bool checkForOverlap(int ax1, int ay1, int ax2, int ay2, int bx1, int by1,
                         int bx2, int by2) {
        return lineSegmentOverlap(ax1, ax2, bx1, bx2) &&
               lineSegmentOverlap(ay1, ay2, by1, by2);
    }

public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1,
                    int bx2, int by2) {
        bool isOverlapped =
            checkForOverlap(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
        if (!isOverlapped) {
            return area(ax1, ay1, ax2, ay2) + area(bx1, by1, bx2, by2);
        }
        int x1 = max(ax1, bx1);
        int x2 = min(ax2, bx2);
        int y1 = max(ay1, by1);
        int y2 = min(ay2, by2);
        return area(ax1, ay1, ax2, ay2) + area(bx1, by1, bx2, by2) -
               area(x1, y1, x2, y2);
    }
};

Happy coding!!!