PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY:MEDIUM PREREQUISITES:Binary Search, Basic math, Data Structures PROBLEM:You have N rectangles of sides L_{i}, B_{i}. You can move them and place them anywhere, but you cannot rotate them. You can also remove M of those rectangles. Finally we take the intersection of left rectangles. What is the maximum possible intersection area. QUICK EXPLANATION:
EXPLANATION:One of the most basic things is that we'll keep left bottom vertices of all rectangles are origin. For example in a way like this(different colors represent different rectangles): This will always give us the maximum intersection area possible. It is a very intuitive result, however we can think like if we increase ycoordinate of any rectangle(keeping everyone else at origin) it'll never cause us profit. First of all let's find intersection area if we can't remove any rectangle: Now that we can remove M rectangles, we will be able to achieve better results since we can increase minimum of lengths and breadths. APPROACH1:An interesting thing to note here will be that if our answer area is A(ie. most optimal solution), any area less than A will also be possible. So, we can do binary search here. For binary search, we'll have to check if an area A is possible to achieve by deleting atmost M rectangles. To check if an area A is possible, we traverse over all rectangles and do the following process: Assuming L_{i} is the minimum length after deletions. So, all rectangles that wouldn't have been deleted would have length greater than L_{i}. Also, since we are achieving area A, all remaining rectangles will have breadth atleast A/(B_{i}). Let's say K is number of rectangles j where L_{j} ≤ L_{i} and B_{j} ≤ A/(B_{i}). If K ≤ M(ie. we have deleted atmost M rectangles), it's possible to achieve this area. So, we have a list of pairs (x_i, y_i) and for a given i, we query: find number of pairs j such that x_j ≤ x_i and y_j ≤ (A/y_i). We'll need to do this for all i. The order in which we do such queries is not important here. AN EASIER APPROACH:An easier approach would be to fix the answer as L * B, we then need to remove all rectangles whose L_{i} < L or B_{i} < B. Note that these L and B belong to one of the rectangles length and breadth(not necessarily the same rectangle). How do we implement this with good complexity? Doing it naively would result in high complexity. Look at this psuedo code for the algorithm:
Complexity: O(N log N + M log N). SOLUTIONS:
This question is marked "community wiki".
asked 19 Jan '15, 01:11

I did it as follows:
answered 19 Jan '15, 15:39

if suppose the ith breadth included comes to the begining of multiset(as per setter code) & later on it is deleted (as u have 1 choice extra ) then in next iteration its length is being considered which has been alredy deleted previously . clarify if i misunderstood something!!! answered 19 Jan '15, 14:23

@darkshadows do you mind explaining the easier approach in more intuitively? I'm just not able to get my head around the logic. Also, are you sorting based on the first value in the pair? Thanks. Regards, Ankit answered 19 Jan '15, 21:59
