Count maximum path in interval list

Question

Given a list of intervals, your task is to count the maximum number of non-overlapping intervals that can be selected. Each interval is defined by a start and end time, and you should return the count of the maximum set of intervals that do not overlap. The input will be a list of intervals represented as pairs of integers, and the output should be a single integer representing the maximum count of non-overlapping intervals.

Codemia · Accepted Answer

The problem requires finding the maximum number of non-overlapping intervals from a given list. This is a classic example of the 'Interval Scheduling Maximization' problem, which can be effectively solved using a greedy approach. The underlying pattern is to prioritize intervals based on their end times rather than their start times, ensuring that we can maximize the number of intervals we can include. By sorting the intervals by their end times, we can use a simple iteration to count how many we can select without overlaps.

1. **Sort the Intervals**: Begin by sorting the list of intervals based on their end times. For example, if we have intervals [(1, 3), (2, 5), (4, 6)], sorting will result in [(1, 3), (2, 5), (4, 6)] as (1, 3) ends first.
2. **Initialize Variables**: Create a counter `count` initialized to 0, and a variable `last_end_time` initialized to track the end time of the last added interval (start with a very small number, e.g., -infinity).
3. **Iterate Through the Intervals**: For each interval, check if the start time is greater than or equal to `last_end_time`. If it is, increment the `count` and update `last_end_time` to the end time of the current interval.
4. **Return the Count**: After iterating through all intervals, return the `count` as the result.

Example: For intervals [(1, 3), (2, 5), (4, 6)], after sorting, we check:
- Interval (1, 3): count = 1, last_end_time = 3
- Interval (2, 5): start (2) < last_end_time (3) -> skip
- Interval (4, 6): start (4) >= last_end_time (3) -> count = 2, last_end_time = 6
Final count is 2.

Here is the Python solution implementing the above approach:

```python
def max_non_overlapping_intervals(intervals):
    # Step 1: Sort intervals based on end times
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end_time = float('-inf')  # Initialize to negative infinity

# Step 2: Iterate through the sorted intervals
    for start, end in intervals:
        if start >= last_end_time:
            count += 1  # Select this interval
            last_end_time = end  # Update the end time

return count
```

This code sorts the intervals and iterates through them while counting the maximum number of 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 sorted list takes O(n), making the overall time complexity O(n log n). The space complexity is O(1) since we are only using a constant amount of space for variables, regardless of the input size.

1. **Empty List**: If the input list is empty, the function should return 0, as there are no intervals to select.
2. **Single Interval**: If there is only one interval, the function should return 1, as that interval can be selected.
3. **All Overlapping Intervals**: If all intervals overlap (e.g., [(1, 3), (2, 4), (3, 5)]), the function should still return 1, as only one interval can be selected.
4. **Non-Overlapping Intervals**: If all intervals are non-overlapping (e.g., [(1, 2), (3, 4), (5, 6)]), the function should return the total number of intervals.

Count maximum path in interval list

OpenAI

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

OpenAI 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