Coding Algorithms — Intervals and Scheduling
Interval and Scheduling problems are some of the commonly asked interview questions in FAANG and other top companies. These problems many times have real use cases and so are favourite of many programmers. If we do not know techniques to solve them quickly it becomes difficult to crack them during interviews.
There are a few tips to solve interval and scheduling problems which I have gathered:
- If intervals are not sorted by start or end time. Its almost always you have to first sort them by either start or end time.
- There are many problems, where you sort the start times and end times separately and merge them in the sorted manner. These gives you the sequence of events that are happening.
- Almost all interval problems can be solved by either doing step 1 or step 2.
- Time complexity in case the intervals are not already sorted is almost always O(N*logN)
Let’s solve a few problems to understand these concepts
Problem 1:
You are given an extra long list. Each element of the list is an array. For example: [[1, 5], [10, 16], [2, 7],….. [1000, 1027]].
The first number of arrays represents the driver’s starting time and the second number is the arrival time for passengers. Given the starting and ending time for online drivers from this input array, find the time interval where there is maximum drivers online. For example, the answer could be [16, 801].
Solution:
If you follow the approach where you first sort the intervals based on start time, then for each interval I, it increases the number of online drivers by 1 for all the intervals [I_start, K], where K ≥ I_start.
This is because the list is sorted by start times and thus I_start is the highest start time seen so far. The maximum online drivers among those is in the interval [I_start, minimum end time ≥ I_start]. We can track the minimum end time using a min heap.
While I_start > min_heap[0], continue popping the root of the min heap.
Time complexity is O(N*logN). Space complexity is O(N).
If we follow the approach where we separately sort the start and end times and merge sort them thus getting the events. Then for each start event number of drivers increase by 1 and for each end event it decreases by 1.
For each event, we only consider the interval from the previous event. Although for maximum online drivers, the previous event must be a start event and current event must be an end event.
Time complexity is O(N*logN). Space complexity is O(N). Although we are using additional space to store the events.
Problem 2:
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] overlaps, merge them into [1,6].
Solution:
Sort the intervals by start time and for each interval I, if I_start < end time of last interval in the output list, then merge I with the last interval, i.e. set the end time of the last interval = max(end time of the last interval, I_end), else just append I to the final output and make it the last interval.
Time complexity is O(N*logN).
Problem 3:
Given a list of intervals A and one interval B, find the least number of intervals from A that can fully cover B. If cannot find any result, just return 0.
Example 1:
Input: A = [[0, 3], [3, 4], [4, 6], [2, 7]] B = [0,6]
Output: 2
Explanation: We can use [0, 3] [2, 7] to cover the B
Solution:
First the intervals are sorted by the start time and for intervals with same start time sort them by higher end time first.
Maintain a stack of the current possible intervals we want to use.
For an interval I, if the end time is smaller than the end time of the last interval in stack then skip I, else if it greater then, we need to find the earliest interval in the stack for which the end time is equal or greater than I_start.
This can be done by either binary search on the end time on intervals in the stack since the end times are in sorted order too in the stack, or popping intervals from the stack till we find one. Popping intervals from stack is advantageous as in, if the intervals were given to us already sorted, then we can accomplish it in O(N) time complexity.
Time complexity is O(N*logN).
Problem 4:
Given A and B two interval lists, A has no overlap inside A and B has no overlap inside B. Write the function to merge two interval lists, output the result with no overlap.
A naive method can combine the two list, and sort and apply merge interval in the leetcode, but is not efficient enough.
For example,
A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]
output [1,6], [8, 20]
Solution:
One solution is to use the events. From the 2 lists, create the merged events using merge sort technique. Keep a counter to track the number of ongoing events.
For each start event increase by 1 and for an end event decrease counter by 1.
For an event, if counter becomes 1 after it, then this is one of the start point of the merged interval and if counter becomes 0 after it then it is the end point of the corresponding start point. Restart again with a new start point whenever counter becomes 1 again.
Another solution just uses the intervals and not the events.
For 2 intervals I and J belonging to the 2 lists, either I’s end is longer than J’s end or J’s end is longer than I’s or both I and J have the same end point.
If I’s end is longer than J’s, we move to the J+1 interval of 2nd list after finding the union of I and J which is [min start(I, J), max end (I, J)] if only min end (I, J) > max start(I, J).
If J’s end is longer than I’s, we move to the I+1 interval of 1st list after finding the intersection of I and J which is [min start(I, J), max end (I, J)] if only min end (I, J) > max start(I, J).
If both I and J have same end, then advance both the list to I+1 and J+1.
We must also merge the final output.
Time complexity is O(N).
Problem 5:
Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any order.
Example :
Input: arrl[] = {1, 2, 9, 5, 5}
exit[] = {4, 5, 12, 9, 12}
First guest in array arrives at 1 and leaves at 4,
second guest arrives at 2 and leaves at 5, and so on.Output: 5
There are maximum 3 guests at time 5.
Solution:
This problem has a very direct use case of using events instead of intervals. We compute the events first and sort them.
Keep a counter to track the number of guests currently in the party. Whenever there is a start event, we increment the number of guests by 1 and whenever there is an end event we decrement the number of guests by 1.
Also we keep track the number of guests at each event to find the time at which the number of guests were maximum.
Time complexity is O(N*logN)
Problem 6:
Define amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.
Solution:
This is a tricky problem, as it does not look to be an interval problem but more of an array problem. But we can transform it to an interval problem.
For each number, compute the minimum and maximum starting indices at which it will be an amazing number.
If A[i] > i, i.e. number is greater than the index, then for all starting indices in the range [i+1, length(A)-A[i]+i], if length(A)-A[i]+i > i, A[i] would be amazing number.
If A[i] < i, i.e. it is already an amazing number, then for starting indices [i+1, length(A)-1] and as well [0, i-A[i]], it will be an amazing number.
After we have computed all the ranges of starting indices for each index ‘i’, we can use the above problem of finding the maximum overlapping point among these ranges and set that as the starting index. It implies that at that starting index maximum number of numbers will be an amazing number.
Time complexity is O(N*logN)
Problem 7:
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]]
Solution:
One solution is to use events. Given that the lists are disjoint and already sorted we can merge these 2 lists into a sorted list of events in O(N) time.
During traversal of the events we maintain a set of which list id the event belongs to. When we see a start event add the list id in the set and when we see an end event remove the list id from the set.
Thus all intersection intervals are the ones where the set contains both the list ids.
Time complexity is O(N).
We can also solve this problem without using the events but using only the intervals. It is similar to merge step in merge sort.
For 2 intervals I and J belonging to the 2 lists, either I’s end is longer than J’s end or J’s end is longer than I’s or both I and J have the same end point.
If I’s end is longer than J’s, we move to the J+1 interval of 2nd list after finding the intersection of I and J which is [max start(I, J), min end (I, J)] if only min end (I, J) > max start(I, J).
If J’s end is longer than I’s, we move to the I+1 interval of 1st list after finding the intersection of I and J which is [max start(I, J), min end (I, J)] if only min end (I, J) > max start(I, J).
If both I and J have same end, then advance both the list to I+1 and J+1.
Time complexity is O(N).
Problem 8:
You are given a shcedule of tasks to work on. Each tasks has a start and an end time [start, end] where end > start. Find out for the given schedule:
- In what intervals you are working (at least 1 task ongoing)
- In what intervals you are multitasking (at least 2 tasks ongoing)
In other words, find union and intersection of a list of intervals. The input is sorted by start time.
Example:
Input: [[1, 10], [2, 6], [9, 12], [14, 16], [16, 17]]Output union: [[1, 12], [14, 17]]
Explanation: We just need to merge overlapping intervalsOutput intersection: [[2, 6], [9, 10]]
Solution:
One solution is to use events. Sort the start and end events first. Keep a counter to track the number of ongoing tasks. Increment the counter by 1 if we see a start event and decrement by 1 if we see an end event.
For the union, we start our tracking whenever we encounter a start event and counter becomes 1 at that event till we find an end event and counter becomes 0 at that event. Repeatedly follow this to find the intervals with at-least one task ongoing.
For the intersection, we start our tracking whenever we encounter a start event and counter becomes 2 at that event till we find an end event and counter becomes 1 at that event. Repeatedly follow this to find the intervals with at-least one task ongoing.
Time complexity is O(N*logN).
Problem 9:
Given a list of processes that can run in parallel. Each process is represented by a triplet [id, startTime, endTime].
A process’s exclusive time is the time spent to execute this process. Note that this does not include the time while multiple processes run simultaneously. Return the exclusive time of each process in the form [id, duration].
Example 1:
Input: [[1, 150, 300], [2, 100, 200], [3, 300, 350]]
Output: [[1, 100], [2, 50], [3, 50]]
Solution:
One solution is to use events. Sort the start and end events first. Keep a counter to track the number of ongoing processes. Increment the counter by 1 if we see a start event and decrement by 1 if we see an end event.
For each start event, if current counter before it was 1, it means there is only one process currently ongoing, increment the processing time of the ongoing process (process associated with the last event).
Associate the process id with each event so it is easy to track the current process.
Similarly if its an end event, and counter is 1, increment the processing time of the ongoing process which is the process associated with the current event.
Time complexity is O(N*logN).
Problem 10:
Given 1-D list of co-ordinates determine if interval (a,b) is covered
Ex — [(2,5), (5,7),(1,4)] and interval = (1,6)
return true
Explanation — Points 1 to 6 lies in list of interval given 1 to 4. 2 to 5 and 5 to 7.[(1,4),(6,7),(2,5)] and interval — (1,6)
return false
Explanation — Distance between 5 to 6 is not covered in the list given so return false
Solution:
One possible solution is to use events. Sort the start and end events. Keep a counter for number of points we have seen so far. For each start event increment the counter by 1 and for each end event decrement the counter by 1.
If for a start event, counter is 0 before this and there was an end event before it, it implies there is a gap and if our target interval had some part in that gap, then return false.
Another solution without using events could be that first merge the given intervals, and then iterate through them. If any part of the target lies in between consecutive intervals, then return false, else return true.
Time complexity is O(N*logN).
Problem 11:
You are standing at the centre of a forest. You can point your camera in any direction and capture photos of trees. Each tree is represented by a polar coordinate Pj in degrees (they are points without dimensions).
Assuming that the camera can take pictures as wide as 90 degrees, which direction should you point your camera to capture the maximum number of trees ?
Solution:
For each tree the minimum and maximum degrees of the camera are [Pj-45, Pj+45] for which it will come under the camera’s field of view.
With these intervals, we can sort the start degrees and end degrees for each tree and merge them to form the sorted events.
Then we maintain a sliding window of size 90 degrees over the sorted events.
If we encounter a new start event at the right end of the sliding window, then we increment the number of trees by 1, and if we are removing an end event from the left end of the sliding window, then decrement the number of trees by 1.
Do nothing if we encounter end event at right end or start event at left end.
Time complexity is O(N*logN)
Problem 12:
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]Solution:
For the i-th tap, it can water the range [i-A[i], i+A[i]], there are 2 possible situations:
- The i-th tap is opened
- The i-th tap is not opened
If the i-th tap is opened, then we can close all taps which already waters within the region [i-A[i], i+A[i]].
Maintain a stack S of open taps.
When a tap is added to the stack of open taps, the left end would be the right end of the last open tap in the stack.
For the i-th tap, first pop from the stack all taps for which the left end ≥ i-A[i], then add the i-th tap to the end of S.
The i-th tap is not opened if the right end of the last open tap in the stack S ≥ i+A[i].
Time complexity is O(N).
