Here are the Blind 75 Interval Algorithm Summaries. See previous post on Graph Algorithms. An "Interval" data structure for the purpose of these Leetcode problems just means an array of Pairs, where each one represents a range of numbers.

Insert Interval

Given an array of non-overlapping sorted interval ranges, add the new input interval range so that the result is still sorted and non-overlapping.

Solution with O(N) time / O(N) space

Create a new array to hold the result. Iterate through the array of interval ranges:

• While the end of the range is less than the start of the new range, insert it into the result
• While the range's start is less than or equal to the new range’s end, build a merged range with the minimum of the existing and new ranges’ start values, and the maximum of the ranges’ end values
• Insert the merged range if built above, or the unmodified new range
• Insert the rest of the ranges afterwards

Merge Intervals

Given an array of possibly overlapping interval ranges, return an array of the same ranges, merged and not overlapping.

Solution with O(NlogN) time / O(N) space

Sort the intervals by start value.

Iterate through, adding the intervals to the output array. If the start value is less than or equal to the previous end value, merge the intervals by updating the existing interval’s end value to the max of the two intervals' end values.

Non-overlapping Intervals

Given an array of possibly overlapping interval ranges, return the number of intervals you would need to remove until the the intervals don’t overlap.

Solution with O(NlogN) time / O(1) space

Sort the intervals by end value.

Iterate through, saving the interval’s end value until an interval’s start value is greater than the saved end value. Count the number of times that the end value was saved (i.e. the number of non-overlapping intervals). The answer is the total intervals from the input minus the number of non-overlapping intervals.

Meeting Rooms

Given an array of possibly overlapping interval ranges, return whether any of the intervals overlap.

Solution with O(NlogN) time / O(1) space

Sort the intervals by start value.

Iterate through, if at any time, the end value of the previous interval is greater than the start value of the current interval, then the answer is yes, they do overlap.

Meeting Rooms II

Given an array of possibly overlapping interval ranges, find the maximum number of overlapping intervals at any point in the intervals.

Solution with O(NlogN) time / O(1) space

Save a sorted array of all the interval start values. Similarly, save the sorted end values.

Think of this like parentheses in algebra, where the start times are left parenthesis, and the end times are the right parenthesis (with the time denoting the placement in the equation).

Iterate through the start values keeping track of two pointers, the depth, and the max depth. For each:

• If the left pointer is less than the right pointer, increment the depth and the left pointer.
• Otherwise, decrement the depth, and increment the right pointer.
• The max depth at any time is the answer.

Check out the next post on Linked Lists