Y
Published on

Leetcode Pattern 3 Intervals

Authors
  • avatar
    Name
    Yinhuan Yuan
    Twitter

Introduction

The sweep line algorithm is a technique used to solve problems related to intervals or segments by "sweeping" a vertical line (or "sweep line") across the plane. As this line moves, we process events that occur at different positions along the line, which allows us to efficiently solve problems that involve intersecting intervals or dynamic changes over time.

  1. Events and Sorting:

    • The core idea of the sweep line algorithm is to break down the problem into discrete events. Each interval generates two events: one for the start and one for the end. We sort these events based on their position.
    • Sorting helps in processing the events in the correct order, ensuring that we handle overlaps and other interactions correctly.

  2. Active Intervals:

    • As the sweep line moves, we maintain a set of active intervals—intervals that are currently being intersected by the sweep line. This set helps us to determine overlaps or compute other relevant properties.

  3. Event Processing:

    • For each event (either a start or an end of an interval), we update our set of active intervals. By processing these events in sorted order, we can efficiently compute results like intersections, unions, and other interval-related properties.

The sweep line algorithm has the following advantages:

  • Efficiency: Sweep line algorithms are efficient for problems involving intervals, often operating in (O(n \log n)) time complexity due to sorting.
  • Versatility: They can be adapted to various interval-related problems by modifying the event processing logic.
  • Clarity: The approach provides a clear and systematic way to handle complex interval interactions.

Intervals Problems

56.Merge Intervals[Medium]

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.

Solution: We start by creating an array where each entry consists of a coordinate and a type: 0 for a starting point and 1 for an ending point. We then sort this array, ensuring that starting points appear before ending points if they are at the same coordinate.

As we sweep through the array, we maintain a count of the number of active intervals. If the type is a starting point, we increase the count by 1; if the type is an ending point, we decrease the count by 1.

When the count reaches 1 at a starting point, it indicates that we are entering a new merged interval, and we record this starting point. Conversely, when the count drops to 0 at an ending point, it signifies that we are exiting a merged interval. We then record this ending point and pair it with the previously recorded starting point to form the resulting interval.

We continue this process until all events are processed.

function merge(intervals: number[][]): number[][] {
    const createNodes = (intervals: number[][]): [number, number][] => {
        const starts: [number, number][] = intervals.map(interval => [interval[0], 0]);
        const ends: [number, number][] = intervals.map(interval => [interval[1], 1]);
        return [...starts, ...ends];
    };
    const nodes = createNodes(intervals);
    nodes.sort((nodeA: [number, number], nodeB: [number, number]) => {
        if (nodeA[0] !== nodeB[0]) return nodeA[0] - nodeB[0];
        return nodeA[1] - nodeB[1]; // starting is infront of ending.
    });
    const ans: number[][] = [];
    let count = 0;
    let start = -1;
    let end = -1;
    nodes.forEach(node => {
        const [coor, type] = node;
        if (type === 0) {
            count += 1;
        } else {
            count -= 1;
        }
        if (count === 1 && type === 0) { // starting point
            start = coor;
        }
        if (count === 0 && type === 1) { // starting point
            end = coor;
            ans.push([start, end]);
        }
    });
    return ans;
};

57.Insert Interval[Medium]

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.

Solution: Similar to the approach used in problem 56, Merge Intervals, we apply the same method to solve this problem.

// Use the function in 56.
function insert(intervals: number[][], newInterval: number[]): number[][] {
    return merge(intervals.concat([newInterval]));
};

986. Interval List Intersections[Medium]

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

Solution: Using a similar approach to problem 56, Merge Intervals, we apply the sweep line algorithm to solve this problem.

When the count reaches 2 at a starting point, it means we are entering an interval where two intervals overlap, so we record this starting point. Conversely, when the count drops to 1 at an ending point, it indicates that we are exiting an interval with two overlapping intervals. We then record this ending point and pair it with the previously recorded starting point to form the resulting interval.

We repeat this process until all events are processed.

function intervalIntersection(firstList: number[][], secondList: number[][]): number[][] {
    const createNodes = (intervals: number[][]): [number, number][] => {
        const starts: [number, number][] = intervals.map(interval => [interval[0], 0]);
        const ends: [number, number][] = intervals.map(interval => [interval[1], 1]);
        return [...starts, ...ends];
    };
    const firstNodes  = createNodes(firstList);
    const secondNodes = createNodes(secondList);
    const nodes = [...firstNodes, ...secondNodes];
    nodes.sort((nodeA: [number, number], nodeB: [number, number]) => {
        if (nodeA[0] !== nodeB[0]) return nodeA[0] - nodeB[0];
        return nodeA[1] - nodeB[1]; // starting is in front of ending.
    });
    let count = 0;
    let ans: number[][] = [];
    let start = -1;
    let end = -1;
    nodes.forEach(node => {
        const [coor, type] = node;
        if (type === 0) {
            count += 1;
        } else {
            count -= 1;
        }
        if (count === 2 && type === 0) {
            start = coor;
        }
        if (count === 1 && type === 1) {
            end = coor;
            ans.push([start, end]);
        }
    });
    return ans;
};

252.Meeting Rooms[Easy]

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Solution: Similar to problem 56, Merge Intervals, we use the sweep line algorithm to address this problem.

One key difference is that in our sorting process, ending points are placed before starting points. This allows for the reuse of meeting rooms after previous meetings have ended.

When the count exceeds 2 at a starting point, it indicates that we cannot schedule the meeting due to a conflict, so we set the final result to false.

We continue this process until all events are processed.

function canAttendMeetings(intervals: number[][]): boolean {
    const createNodes = (intervals: number[][]): [number, number][] => {
        const starts: [number, number][]  = intervals.map(interval => [interval[0], 0]);
        const ends: [number, number][] = intervals.map(interval => [interval[1], 1]);
        return [...starts, ...ends];
    };
    const nodes = createNodes(intervals);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - a[1]; // // ending is in front of starting.
    });
    let count = 0;
    let ans = true;
    nodes.forEach(node => {
        const [coor, type] = node;
        if (type === 0) {
            count += 1;
        } else {
            count -= 1;
        }
        if (count >= 2) {
            ans = false;
        }
    });
    return ans;
};

253. Meeting Rooms II[Medium]

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Solution: Similar to problem 252, Meeting Rooms [Easy], we use the sweep line algorithm to solve this problem, with ending points placed before starting points in the sorting of events.

We track changes in the count of active intervals and update the final result if the count exceeds the allowed limit.

We repeat this process until all events have been processed.

function minMeetingRooms(intervals: number[][]): number {
    const createNodes = (intervals: number[][]): [number, number][] => {
        const starts: [number, number][] = intervals.map(interval => [interval[0], 0]);
        const ends: [number, number][] = intervals.map(interval => [interval[1], 1]);
        return [...starts, ...ends];
    };
    const nodes = createNodes(intervals);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - b[0]; // put the ending in front of starting.
    });
    let count = 0;
    let ans = 0;
    nodes.forEach(node => {
        const [coor, type] = node;
        if (type === 0) {
            count += 1;
        } else {
            count -= 1;
        }
        ans = Math.max(count, ans);
    });
    return ans;
};

1094. Car Pooling[Medium]

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Solution: Similar to problem 252, Meeting Rooms [Easy], we use the sweep line algorithm to solve this problem, sorting events with ending points placed before starting points.

Instead of tracking the count of active intervals, we track the number of passengers. We determine the maximum number of passengers at any point.

We continue this process until all events have been processed and then compare the maximum number of passengers with the car capacity.

function carPooling(trips: number[][], capacity: number): boolean {
    const createNodes = (trips: number[][]): [number, number, number][] => {
        const starts: [number, number, number][] = trips.map(trip => [trip[1], 0, trip[0]]);
        const ends:   [number, number, number][] = trips.map(trip => [trip[2], 1, trip[0]]);
        return [...starts, ...ends];
    };
    const nodes = createNodes(trips);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - b[0]; // put the ending in front of starting.
    });
    let count = 0;
    let ans = 0;
    nodes.forEach(node => {
        const [coor, type, numPassagers] = node;
        if (type === 0) {
            count += numPassagers;
        } else {
            count -= numPassagers;
        }
        ans = Math.max(ans, count);
    });
    return capacity >= ans;
};

759.Employee Free Time[Hard]

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.

Solution: Similar to problem 252, Meeting Rooms [Easy], we use the sweep line algorithm to solve this problem, with events sorted such that ending points are placed before starting points.

When the count of active intervals decreases to 0 after encountering an ending point, it signifies the start of a new interval. When the count increases to 1 after encountering a starting point, this interval ends, and we add it to the final result.

We repeat this process until all events have been processed.

function employeeFreeTime(schedule: Interval[][]): Interval[] {
    const createNodes = (schedule: Interval[][]): [number, number][] => {
        let ans: [number, number][] = [];
        for (let i = 0; i < schedule.length; i++) {
            for (let j = 0; j < schedule[i].length; j++) {
                ans.push([schedule[i][j].start, 0]);
                ans.push([schedule[i][j].end, 1]);
            }
        }
        return ans;
    };
    const nodes = createNodes(schedule);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - a[1]; // put the ending in front of starting.
    });
    let count = 0;
    let start = -1;
    let end = -1;
    let ans: Interval[] = [];
    nodes.forEach(node => {
        const [coor, type] = node;
        if (type === 0) {
            count += 1;
        } else {
            count -= 1;
        }
        if (count === 0 && type === 1) { // ending
            start = coor;
        }
        if (count === 1 && type === 0) { // starting
            end = coor;
            if (start !== -1 && start !== end) {
                ans.push(new Interval(start, end));
            }
        }
    });
    return ans;
};

2251. Number of Flowers in Full Bloom[Hard]

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the ith flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the ith person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the ith person arrives.

Solution: We begin by creating an array of events, where each entry consists of a coordinate and a type: 0 for a starting point and 1 for an ending point. We then sort this array, ensuring that starting points are placed before ending points if they occur at the same coordinate.

We also create a hash map, memo, to store the values from the people array, and an array of unique values from the people array.

As we sweep through the events, we maintain a count of active intervals. If the event is a starting point, we increment the count by 1. Before incrementing, we update the memo if the current value is less than the current day minus 1. If the event is an ending point, we decrement the count by 1. Before decrementing, we set all uniquePeople[k] in the memo.

We continue this process until all events are processed. Finally, we update the remaining values in uniquePeople in the memo, convert the memo to an array, and return it.

function fullBloomFlowers(flowers: number[][], people: number[]): number[] {
    const createNodes = (flowers: number[][]): [number, number][] => {
        const starts: [number, number][] = flowers.map(flower => [flower[0], 0]);
        const ends: [number, number][] = flowers.map(flower => [flower[1], 1]);
        return [...starts, ...ends];
    };
    const nodes = createNodes(flowers);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    const uniquePeople = [...new Set(people)];
    uniquePeople.sort((a, b) => a - b);
    let count = 0;
    let k = 0;
    const memo: Map<number, number> = new Map();

    nodes.forEach(node => {
        const [day, type] = node;
        if (type === 0) { // starting node
            // From k value to day - 1, all the values should be count.
            // Since day, it becomes count + 1
            while (uniquePeople[k] <= day - 1) {
                memo.set(uniquePeople[k], count);
                k += 1;
            }
            count += 1;
        } else {// ending node
            // From k value to day, all the values should be count.
            // Since day + 1, it becomes count - 1;
            while (uniquePeople[k] <= day) {
                memo.set(uniquePeople[k], count);
                k += 1;
            }
            count -= 1;
        }
    });
    // Set the rest of values.
    for (let i = k; i < uniquePeople.length; i++) {
        memo.set(uniquePeople[i], count);
    }
    return people.map(i => memo.get(i)!);
};

452. Minimum Number of Arrows to Burst Balloons[Medium]

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Solution: We start by sorting the balloons based on their ending points. We select the ending point of the first balloon as the position for the first arrow. Then, we iterate through the list of balloons. If a balloon's starting point exceeds the current arrow's ending point, it means the current arrow cannot cover this balloon. In this case, we place a new arrow at the ending point of the current balloon.

We repeat this process for all balloons and return the total number of arrows needed as the result.

// Greedy Algorithm
function findMinArrowShots(points: number[][]): number {
    points.sort((a: number[], b: number[]) => a[1] - b[1]); // Sort by ending point
    let ans = 1;
    let arrowPoint = points[0][1];
    points.forEach(point => {
        const start = point[0];
        const end = point[1];
        if (start > arrowPoint) {
            // If the current interval can be to cut by the current arrow point
            ans += 1;
            arrowPoint = end;
        }
    });
    return ans;
};

436. Find Right Interval[Medium]

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Solution: We begin by creating an array of events, where each entry includes a coordinate and a type: 0 for a starting point and 1 for an ending point. We then sort this array, ensuring that ending points are placed before starting points when they occur at the same coordinate.

As we sweep through the events, we maintain a set of active intervals. When encountering an ending point, we add the associated index to the set. When encountering a starting point, we access the set of indices collected for ending points and assign the index of this starting point to the next interval.

We repeat this process until all events have been processed.

function findRightInterval(intervals: number[][]): number[] {
    const createNodes = (intervals: number[][]): [number, number, number][] => {
        const starts: [number, number, number][] = intervals.map((interval, index) => [interval[0], 0, index]); // use 0 for the type of starts
        const ends: [number, number, number][] = intervals.map((interval, index) => [interval[1], 1, index]); // use 1 for the type of ends to make sure the ends will be reach earily than starts with the same coordinates.
        return [...starts, ...ends];
    };
    const n = intervals.length;
    const nodes = createNodes(intervals);
    nodes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - a[1]; // Put the ending point before the starting point.
    });
    const ans = Array(n).fill(-1);
    let ends: Set<number> = new Set();
    nodes.forEach(node => {
        const [coor, type, index] = node;
        if (type === 1) { // it is an end
            ends.add(index);
        } else {
            ends.forEach(i => ans[i] = index);
            ends = new Set();
        }
    });
    return ans;
};
Discuss on Twitter • View on GitHub