Frontend School

Minimum Time to Fulfill Orders

DSA
medium

Minimum Time to Fulfill Orders

Medium
Binary Search
Arrays

Overview

Myntra's fulfillment centers handle a massive volume of orders daily. To optimize customer satisfaction and operational efficiency, it's crucial to minimize the total time taken to process all pending items. We have multiple processing units, each with a specific time it takes to process a single item. This problem focuses on determining the shortest possible time required to process a given total number of items by leveraging these units in parallel.

What you need to do / Task

Implement a function minTimeFulfillOrders that calculates the minimum time required to process totalItems given an array of processingTimes. Each value processingTimes[i] represents the time (in minutes) the i-th processing unit takes to process one item.

Input & output

  • processingTimes: An array of positive integers, where processingTimes[i] is the time (in minutes) the i-th processing unit takes to process one item.
  • totalItems: A positive integer representing the total number of items that need to be processed.
  • Return: A single integer, the minimum time (in minutes) required to process all totalItems.

Clarifications

  • All processing units work independently and in parallel.
  • A unit processing an item takes processingTimes[i] minutes. If a unit works for T minutes, it can process floor(T / processingTimes[i]) items.
  • The goal is to find the minimum T such that the sum of items processed by all units in T minutes is greater than or equal to totalItems.

Examples

1

Example 1

Input:

processingTimes = [1, 2, 3], totalItems = 5

Output:

3

Note:

At time = 1: Unit 1 processes 1 item. Total 1 item. At time = 2: Unit 1 processes 2 items, Unit 2 processes 1 item. Total 3 items. At time = 3: Unit 1 processes 3 items, Unit 2 processes 1 item, Unit 3 processes 1 item. Total 5 items. Since 2 minutes is not enough (only 3 items) and 3 minutes is enough (5 items), the minimum time is 3.

2

Example 2

Input:

processingTimes = [1, 2, 3], totalItems = 10

Output:

6

Note:

At time = 5: Unit 1 processes 5 items, Unit 2 processes 2 items, Unit 3 processes 1 item. Total 5 + 2 + 1 = 8 items. Not enough. At time = 6: Unit 1 processes 6 items, Unit 2 processes 3 items, Unit 3 processes 2 items. Total 6 + 3 + 2 = 11 items. This is >= 10. Since 5 minutes is not enough and 6 minutes is enough, the minimum time is 6.

3

Example 3

Input:

processingTimes = [1000000000], totalItems = 500000

Output:

500000000000000

Note:

With only one unit taking 10^9 minutes per item, to process 500,000 items, it will take 500,000 * 10^9 = 5 * 10^14 minutes.

Constraints

Constraints & assumptions

  • 1 <= processingTimes.length <= 10^5
  • 1 <= processingTimes[i] <= 10^9
  • 1 <= totalItems <= 10^6
  • The answer will fit within a standard 64-bit floating-point number's integer precision (e.g., JavaScript's number type, up to 2^53 - 1).

What interviewers evaluate

  • Correctness and efficiency of the binary search implementation.
  • Ability to formulate the check function for binary search effectively.
  • Handling of edge cases and large input values within the given constraints.
  • Code clarity, structure, and adherence to best practices.

Loading editor...