Shared Warming Drawer Range

Intersection of closed integer intervals and a given interval

EasyIntervalsIntersection

A recipe app is helping you hold several dishes in one warming drawer. The drawer must use a single integer temperature setting for every dish.

Each dish has an acceptable closed temperature range. In ranges, the pair [low, high] means that dish can be held at any integer setting from low through high, inclusive. The pair drawer gives the drawer's own supported range in the same format.

Return a two-element list [lowest, highest] describing all settings supported by the drawer and acceptable for every dish. If no setting works, return an empty list.

A range consisting of just one setting is valid. If there are no dishes, every setting supported by the drawer is acceptable.

Examples

Example 1

Input: ranges = [[50,80],[60,90]], drawer = [40,75]
Output: [60,75]

The dishes' acceptable ranges overlap within the drawer's supported range. The returned range includes exactly the settings shared by all three ranges.

Example 2

Input: ranges = [[30,40],[45,60]], drawer = [20,80]
Output: []

The first dish requires a setting below every setting acceptable for the second dish, so no shared setting exists.

Example 3

Input: ranges = [], drawer = [35,85]
Output: [35,85]

There are no dishes to impose additional restrictions, so the drawer's entire supported range remains available.

Constraints

  • 0 <= ranges.length <= 1800
  • Each element of ranges and drawer contains exactly two integers.
  • -1000000 <= low <= high <= 1000000 for every range, including drawer.

All endpoints are inclusive. Negative values are valid settings on the app's temperature scale. The input ranges need not be sorted.

Hints

Show hint 1

A setting must be at least every lower endpoint and at most every upper endpoint.

Show hint 2

Track the tightest lower and upper limits. Equality between those limits still permits one setting.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you report the number of valid integer settings instead of the range?
  • How would you maintain the answer efficiently if dishes were only added, never removed?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem