Minimum Points Hitting Every Closed Interval
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
You are given closed integer intervals [left,right]. Choose a minimum-size set of integer points so every interval contains at least one chosen point.
Return the canonical greedy solution in increasing order: sort intervals by increasing right endpoint (then increasing left endpoint), and whenever the current interval is not covered, choose its right endpoint.
Function
minimumHittingPoints(intervals: int[][]) → int[]Examples
Example 1
intervals = [[1,3],[2,5],[3,6]]return = [3]Point 3 lies in every interval.
Example 2
intervals = [[1,2],[3,4],[2,3]]return = [2,4]The first uncovered interval chooses 2; the later interval [3,4] is uncovered and chooses 4.
Example 3
intervals = []return = []No intervals require no points.
Constraints
0 <= intervals.length <= 200000.-10^9 <= left <= right <= 10^9.