Dynamic Programming on interval list

Question

Given a list of intervals, implement a dynamic programming solution to find the maximum number of non-overlapping intervals that can be selected. Each interval is represented as a pair of integers [start, end], and your function should return an integer representing the maximum count of non-overlapping intervals. The input will be a list of these intervals, and the output should be a single integer.

Codemia · Accepted Answer

The problem of finding the maximum number of non-overlapping intervals can be identified as an optimization problem that is best solved using a greedy algorithm rather than traditional dynamic programming. The key pattern here is that we need to maximize the number of intervals selected while ensuring that none overlap. The greedy strategy involves sorting the intervals by their end times. By always choosing the interval that ends the earliest, we leave as much room as possible for subsequent intervals. This strategy is effective because selecting the interval that finishes first minimizes the time occupied, thereby maximizing the potential for including more intervals.

1. **Sort the Intervals**: Start by sorting the list of intervals based on their end times. For example, given intervals [[1, 2], [2, 3], [3, 4], [1, 3]], after sorting, we would have [[1, 2], [1, 3], [2, 3], [3, 4]].
2. **Initialize a Counter and Tracker**: Create a variable to count the maximum number of non-overlapping intervals and a variable to track the end time of the last selected interval. Initialize the counter to 0 and the last end time to a very small number (e.g., -inf).
3. **Iterate through the Sorted Intervals**: For each interval in the sorted list, check if its start time is greater than or equal to the last selected end time. If it is, increment the counter and update the last end time with the current interval's end time. For the example above, we would select [1, 2] first, then [2, 3], and finally [3, 4].
4. **Return the Counter**: After iterating through all intervals, return the counter which holds the maximum number of non-overlapping intervals.

Here is the Python implementation of the above approach:
```python
def maxNonOverlappingIntervals(intervals):
    # Step 1: Sort intervals by end time
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')

# Step 2: Iterate through sorted intervals
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end

return count
```
This code correctly implements the greedy approach for selecting non-overlapping intervals.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of intervals. The subsequent iteration through the intervals takes O(n), making the overall complexity dominated by the sorting step. The space complexity is O(1) since we are using a constant amount of space for the counter and last_end variable, aside from the input list.

1. **Empty Input**: If the input list is empty, the output should be 0 since there are no intervals to select. 
2. **All Overlapping Intervals**: For intervals like [[1, 2], [1, 3], [1, 4]], the function should return 1, as only one interval can be selected. 
3. **Fully Nested Intervals**: If the intervals are fully nested, like [[1, 5], [2, 3], [4, 5]], the output should still be 2, as we can select [2, 3] and [4, 5]. 
4. **Single Interval**: If there is only one interval, such as [[1, 2]], the output should be 1, as that interval can be selected.

Dynamic Programming on interval list

Goldman Sachs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Goldman Sachs Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string