Frontend School

Calculate Peak Delivery Time

DSA
medium

Calculate Peak Delivery Time

Medium
Intervals
Sorting
Two Pointers

Overview

At Zomato, optimizing delivery logistics is crucial for customer satisfaction and operational efficiency. One challenge is identifying periods when both restaurants are experiencing high demand and delivery partners are readily available. This problem focuses on calculating the total duration of these 'peak delivery' windows to help in resource allocation and demand forecasting.

What you need to do / Task

You are given two lists of time intervals: one representing periods when a restaurant anticipates high demand, and another representing periods when delivery partners are available. Your task is to find the total combined duration (in minutes) when both the restaurant is experiencing high demand and delivery partners are available.

Deliverables:

  1. Implement a function that takes two lists of intervals as input.
  2. Calculate the intersection of these two sets of intervals.
  3. Merge any overlapping or contiguous intersected intervals into a single, combined interval.
  4. Return the sum of the lengths of these final merged intervals.

Input & output

Input:

  • restaurantIntervals: An array of [start, end] tuples, where start and end are integers representing minutes from midnight (0 to 1440). Each interval [start, end) is inclusive of start and exclusive of end. These represent periods of high restaurant demand.
  • deliveryPartnerIntervals: An array of [start, end] tuples, in the same format as restaurantIntervals. These represent periods when delivery partners are available.

Output:

  • A single integer representing the total number of minutes during which both conditions (high restaurant demand and delivery partner availability) are met.

Clarifications

  • All time intervals are within a single 24-hour day (0 to 1440 minutes).
  • Intervals [start, end) means start <= time < end.
  • Input interval lists may not be sorted.
  • If there are no common availability periods, the function should return 0.
  • An interval like [100, 150) has a duration of 50 minutes.

Examples

1

Example 1

Input:

restaurantIntervals = [[900, 1000], [1100, 1200]], deliveryPartnerIntervals = [[950, 1050], [1030, 1130]]

Output:

80

Note:

Restaurant is available from 900-1000 and 1100-1200. Delivery partners are available from 950-1050 and 1030-1130. The shared availability periods are [950, 1000) and [1100, 1130), summing to 50 + 30 = 80 minutes.

2

Example 2

Input:

restaurantIntervals = [[900, 1100]], deliveryPartnerIntervals = [[950, 1000], [980, 1050]]

Output:

100

Note:

Restaurant is available from 900-1100. Delivery partners are available from 950-1000 and 980-1050. The shared availability periods are [950, 1000) and [980, 1050), which merge into a single continuous period of [950, 1050), summing to 100 minutes.

3

Example 3

Input:

restaurantIntervals = [[100, 200]], deliveryPartnerIntervals = [[300, 400]]

Output:

0

Note:

There are no overlapping times when both the restaurant is available and delivery partners are available.

Constraints

Constraints & assumptions

  • 0 <= start < end <= 1440 for all intervals.
  • The number of intervals in restaurantIntervals (N) and deliveryPartnerIntervals (M) will be between 0 and 10^4.
  • Intervals are given as [start, end) where start and end are integers.

Out of scope

  • Handling intervals that span across midnight (e.g., [2300, 100]).
  • Real-time updates or concurrent interval management.

What interviewers evaluate

  • Correctness: The solution accurately identifies and sums all peak delivery times.
  • Efficiency: The algorithm chosen is optimal in terms of time and space complexity for the given constraints.
  • Robustness: Handles edge cases such as empty inputs, no overlaps, or multiple complex overlaps.
  • Code Quality: The code is well-structured, readable, and follows good programming practices.

Loading editor...