Need help in a question on Binary Search

general
1

Question on Binary Search

Hi, I’ve been trying to solve Apartments from cses.fi problem set.

I have tried the following approaches :

Approach 1 : using multiset (TLE)

Approach 2 : Assigning apartments from the lower limit (a[i] - k) of desired apartment size C++ 's lower_bound(). Then marking them off as an apartment is assigned. (incorrect)

Help me solve this problem. Thanks.

2

Have you first copied unassigned apartments in b. And then assigning apartments from the lower limit (a[i]−k).
And Please share your code using ideone. It would be easy to figure out error(Approach 2).

Use sort to sort both unassigned apartments and required size. And then use 2 pointer approach.

Because first assigning apartment and then proceeding on to larger. Would be helpful.

1 Like