Problem Name — "Group Photo"
There are $$$N$$$ people, each with a unique height. The height of the $$$i^{th}$$$ person is $$$i (1 \leq i \leq N)$$$. The $$$i^{th}$$$ person will smile in the photo if at least $$$A[i]$$$ people in the photo are shorter than him and at most $$$B[i]$$$ people in the photo are taller than him.
Find the largest group such that everyone will smile in the photo of this group. A group is a collection of randomly selected people from the given $$$N$$$ people.
Constraints:
$$$1 \leq N \leq 10^5$$$
$$$0 \leq A[i], B[i] \leq N$$$
Example Test Case
My O(N^2) approach
I cannot come up with a better solution for this. Any help would be greatly appreciated, thanks!
Binary Search on the number of people. Also this is a Codeforces problem.
i got idea of binary search but didn't get to know how i made the function
Can you give the link or you can tell the approach . thanks in advance
Found the problem
Thanks brother
Use binary search on the answer.
Using binary search check if a group of a number of people are happy. To do that take people in increasing order of their heights. Consider the ith person, his height will be i, so we should have at least a[i] persons shorter than him i.e, we should already have taken at least a[i] persons before him (
number_of_people_included >= a[i]
), then check if there is room fornum - number_of_people_included
taller people inside the group (num - number_of_people_included <= b[i]
).num
is the number of persons in a group.Plzz share the code in spoiler tag. Thanks in advance
Wow, it seems so easy now, yet it never occurred to me during the contest to use binary search. Thanks a lot!
ohh means loop [1..n] --> check for i that A[i] >= no. of choosen before and B[i] < (avilable space) Right??