Uber 电面题目求更好的解法

Given a list of tuples consisting of interval start and end time (both inclusive), find a set of numbers with minimum size such that at least k numbers from each interval are covered. Start by choosing k = 2. You can assume each interval will have size at least k.

Examples for k = 2:
[[1,4], [5,6]] - [1,4,5,6]
[[1,4], [3,6], [2,4]] - [3,4]
[[1,2], [2,3], [2,5]] - [1,2,3]
[[1,10], [3,7], [5,6]] - [5,6]
[[1,5], [4,7], [6,8], [9,13]] - [4,5,6,7,9,13]
[[1,10], [5,7], [7,13]] - [6,7,8]

I used a modification of interval intersection to identify common elements and propogate it through the sorted list. Was able to generate a linear solution for k=2 (if the list is already sorted, otherwise nlogn).

不知道有没有更好的写法