Find minimum cost in interval list

Question

Given a list of intervals represented by their start and end points, find the minimum cost to cover all intervals using a specified cost function. The function should take the list of intervals as input and return the minimum cost as output. Ensure that your solution is efficient and handles edge cases, such as overlapping intervals.

Codemia · Accepted Answer

To find the minimum cost to cover all given intervals, we can recognize that this problem is best approached using a sorting strategy combined with a greedy algorithm. The primary pattern here is to sort the intervals by their start points. Once sorted, we can iterate through the intervals and determine the minimum cost based on their overlaps. The reason a greedy approach works here is that once we have sorted the intervals, we can make local optimal choices (i.e., covering overlapping intervals) that lead us to a global optimum (i.e., the minimum cost to cover all intervals).

1. **Sort the Intervals**: First, we sort the list of intervals based on their start points. If two intervals have the same start point, we can further sort by their end points. For example, given intervals `[(1, 3), (2, 4), (3, 5)]`, sorting them results in the same order since they are already sorted.  
2. **Initialize Variables**: We will maintain a variable to track the current end of the covered interval and a total cost variable initialized to 0.  
3. **Iterate Through Intervals**: For each interval, check if it overlaps with the current covered interval (i.e., if the start of the current interval is less than or equal to the end of the last covered interval). If it does overlap, update the end of the covered interval to be the maximum of its current end and the end of the overlapping interval. If it does not overlap, add the cost of covering the current interval (which can be defined as the length of the interval) to the total cost and update the current end to this interval's end.  
4. **Return Total Cost**: After processing all intervals, return the total cost. For example, with intervals `[(1, 3), (2, 4), (3, 5)]`, the total cost would be the sum of lengths of non-overlapping intervals.

Here is the Python code that implements the above approach:
```python
def min_cost_to_cover_intervals(intervals):
    if not intervals:
        return 0  # edge case for empty input
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: (x[0], x[1]))
    
    total_cost = 0
    current_end = intervals[0][1]  # end of the first interval
    
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start <= current_end:
            # Overlapping intervals; extend the current covered interval
            current_end = max(current_end, end)
        else:
            # No overlap; add the cost of the previous interval and reset
            total_cost += current_end - intervals[i-1][0]  # cost is the length of the last covered interval
            current_end = end  # update the current end to the new interval's end
    
    # Add the cost of the last interval
    total_cost += current_end - intervals[-1][0]
    
    return total_cost
```

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 sorted list is O(n), making the overall complexity dominated by the sorting step. The space complexity is O(1) if we do not consider the space used by the input list, as we are only using a few extra variables for tracking the total cost and current end.

1. **Empty Input**: If the input list is empty, the function should return 0, as there are no intervals to cover.  
2. **Single Interval**: If there is only one interval, the cost should simply be the length of that interval. For example, for the interval `[(5, 10)]`, the function should return `10 - 5 = 5`.  
3. **All Overlapping Intervals**: If all intervals overlap, we should ensure that the cost is calculated as the length of the overall coverage rather than the sum of individual interval lengths. For example, intervals `[(1, 5), (2, 3), (4, 6)]` should return `6 - 1 = 5`.

Find minimum cost in interval list

Supabase

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

Supabase 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