Count kth largest element in interval list

Question

Given a list of intervals, each defined by a start and end point, write a function to find the k-th largest element among all the endpoints of these intervals. The function should take in a list of intervals and an integer k, and return the k-th largest endpoint as an integer. If k is greater than the number of unique endpoints, return -1.

Codemia · Accepted Answer

To solve the problem of finding the k-th largest endpoint among a list of intervals, we can utilize a combination of a set and a sorting method. The main challenge is to efficiently gather all unique endpoints (both start and end points) from the intervals. Once we have a collection of unique endpoints, we can sort them in descending order and find the k-th largest element. This approach is suitable as it requires manipulating a collection of numbers (the endpoints), making it ideal for sorting-based techniques.

Here’s a step-by-step approach to the problem:
1. **Extract Endpoints**: Iterate through the list of intervals, and for each interval, add its start and end points to a set to ensure uniqueness.
   - For example, given intervals [(1, 5), (2, 3), (5, 7)], the unique endpoints collected would be {1, 2, 3, 5, 7}.
2. **Convert to List**: Convert the set of unique endpoints back into a list for sorting.
3. **Sort the List**: Sort the list of unique endpoints in descending order to easily access the k-th largest element.
   - From the previous example, after sorting, we would have [7, 5, 3, 2, 1].
4. **Return the k-th Largest**: Check if k is valid (i.e., less than or equal to the number of unique endpoints). If valid, return the k-th largest element; otherwise, return -1.

Here is the Python code that implements the above approach:
```python
def kth_largest_endpoint(intervals, k):
    unique_endpoints = set()
    for start, end in intervals:
        unique_endpoints.add(start)
        unique_endpoints.add(end)
    sorted_endpoints = sorted(unique_endpoints, reverse=True)
    if k > len(sorted_endpoints):
        return -1
    return sorted_endpoints[k - 1]
```
This function first collects unique endpoints, sorts them in descending order, and returns the requested k-th largest endpoint.

The time complexity of this solution is O(n log n), where n is the number of unique endpoints. This is due to the sorting step, as we need to sort the unique endpoints after extracting them from the intervals. The space complexity is O(u), where u is the number of unique endpoints stored in the set. This accounts for the space used to store unique values before sorting.

1. **Empty Input**: If the list of intervals is empty, the function should return -1 since there are no endpoints.
2. **Single Interval**: If there is only one interval, the function should correctly return the k-th largest based on its start and end points.
3. **k Greater than Unique Endpoints**: If k is greater than the number of unique endpoints, the function should return -1 as specified. For example, if intervals = [(1, 4), (2, 5)] and k = 3, the return should be -1 since there are only two unique endpoints (1, 2, 4, 5).

Count kth largest element in interval list

Plaid

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

Plaid 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