An uber test question

general
1

so this question was recently asked form my friend so to dont have the exact question but ill try to explain it the best i can…

there is a factory which produces stones it runs for N days
the num of stones produced in ith day is ai
an array containing [a1, a2 ,…,an] is given

ith stone is only valid for bi days
an array [b1,b2,…bn] is also given

you have to tell the maximum num of stones which are valid at one instant/day

eg:
num of days : 4
arr of production : 3 1 0 2
arr of validity : 2 4 0 8

so the 3 stones produced in the first day last 2 days the stone produced in day 2 lasts for 4 days

so till now num stones valid are 3(for fist day) 4(adding the newly produced stone)

but on the 3rd day the validity of the stones on first day is over so on the 3rd day only 1 stone(produced at day 2) is valid and so on

in this case the maximum stone valid at one day/instance is 4(at day 2)

this can easily be solved in O(n^2) but that solution gives a TLE so i need a more optimized way to solve this

2

You can check my code and if u find error in it le me know :sweat_smile: :sweat_smile:

3

A simple way to think of it can be,
suppose on i th day ai items are produced with di validity. put it in priority queue (min heap) with pair { ai, di + i - 1 (its expiry) }
and on reaching every i th day pop out elements which are expired by comparing day and their expiry.

max of priority queue size(including total elements), in all states will be answer

4

so the priority queue stores the expiry dates in decreasing order and to pop we only need O(1)
but i dont understand what are you doing to get the answer

sry i am not familiar with STL so a small example would be great…