Prerequisites: Greedy/ Dynamic Programming
Explanation: First, lets have an easy observation that it is always optimal to arrange the couples first. As there are too many queries so we will precalculate the maximum number of places for couples. That can be calculated greedily or using dynamic programming.
Greedy Technique: At first, think we have matrix. We will try to fill columns and rows with couples respectively. This is always optimal to take column first, why? Let the current status of the matrix is
If we fill up the 1st row with a couple then if there were another column like this, then we won’t able to fill it up with another couple here. But if we take column first instead of row then we will fill 1st column with couple and there will be still remain a chance to fill the 1st row with a couple. Finally, the matrix that we are considering can be filled with maximum couples.
Before placing couples.
After placing couples.
So, we will iterate through left to right (also can iterate through right to left) and fill all matrix with couples optimally and we will get maximum number of couples that can be placed.
Dynamic Programming: DP will have two states indicating current column and the value assigned in previous column. Thus we can calculate maximum places for couples.
Time Complexity: For precalculation, and answering queries in .