Remove Covered Intervals
Medium · Intervals · about 15 minutes
Asked at Microsoft, Amazon, Bloomberg, Google.
Each entry [l, r] of intervals stands for the half-open interval [l, r), and no two entries are equal. An interval is redundant when some other interval contains it entirely: [a, b) lies inside [c, d) when c <= a and b <= d. Drop every redundant interval and report how many are left.