Choose the best flask type

A robotic chemical delivery system in a college laboratory uses only one type of glass flask per day. Each chemical order must be filled with a mark that is at least equal to the volume ordered. There are multiple flask types available, such as with various marks and various loads.

Given a list of order requirements and a list of flasks with their measurements, determine which single type of flask will result in minimal waste. Waste is calculated as the sum of (marking - requirement) for each order.

Return the zero-based index of the chosen flask type. If multiple flask types have the same minimal waste, return the one with the lowest index. If no flask can satisfy all requirements, return -1.

Example 1:

Input:[[4,6],2,[[0,5],[0,7],[1,4],[1,10]]]

Output:0

Example 2:

Input:[[10,15],3,[[10,11],[0,20],[1,17],[1,12],[2,16]]]

Output:1

Constraints:

1 <= n <= 10^5
1 <= flaskTypes <= 10^4
1 <= totalMarks <= 10^5
1 <= requirements[i] <= 10^7 (where 0 <= i < n)
0 <= markings[i][j] < flaskTypes (where 0 <= i < totalMarks)
0 <= markings[i][j] < 10^5 (where 0 <= i < totalMarks)

solution.cpp

Run code to see test results

00:00 / 69:42

Choose the best flask type

HardMed•338 views

Return the zero-based index of the chosen flask type. If multiple flask types have the same minimal waste, return the one with the lowest index. If no flask can satisfy all requirements, return -1.

Example 1:

Input:[[4,6],2,[[0,5],[0,7],[1,4],[1,10]]]

Output:0

Example 2:

Input:[[10,15],3,[[10,11],[0,20],[1,17],[1,12],[2,16]]]

Output:1

Constraints:

1 <= n <= 10^5
1 <= flaskTypes <= 10^4
1 <= totalMarks <= 10^5
1 <= requirements[i] <= 10^7 (where 0 <= i < n)
0 <= markings[i][j] < flaskTypes (where 0 <= i < totalMarks)
0 <= markings[i][j] < 10^5 (where 0 <= i < totalMarks)

HardMed•338 views

Time Complexity

Space Complexity

Asked at

SCA (Standard Chartered)

Author: Amit Dayal

Software Engineer

Expert in Data Structures & Algorithms. Building tools to help developers crack FAANG interviews.