Find the minimum number of rectangles left after inserting one into another

0 0 7 minutes read

Given width and height of N rectangles. The task is to find the minimum number of rectangles left after inserting one into another.
Note :

If W1 < W2 and H1 < H2 then rectangle 1 fits inside rectangle 2.
The smallest rectangle can insert in the second smallest, and this rectangle can insert in the next one and so forth.

Examples:

Input : arr[] = {{20, 30}, {10, 10}, {30, 20}, {40, 50}};
Output : 2
Explanation : One of the possible way is to insert 
second rectangle in first and then insert 
first rectangle in fourth. 
Then finally, third and fourth rectangles left.

Input : arr[] = {{10, 30}, {20, 20}, {30, 10}};
Output : 3
Explanation : Can't place any rectangle in any other one. 
So, three rectangles left.

Approach :

Firstly sort all rectangles such that the heights are in decreasing order. We will first assume that each height is unique (later we will extend our approach to the case where there are the same heights).
We maintain another array nested[i]. Starting from the tallest rectangle down to the shortest, we will try to fit in the rectangle to nested[i], by finding a nested rectangle in nested[i] in which its width is bigger than that of our current rectangle. Not only that, we want to place it in the one with the minimum width. We then place the rectangle inside that nested rectangle and update its new height and weight. Why the minimum one? Because if we place the rectangle on another one with a width bigger than that of minimum width, we can apply the following exchange argument:
Let’s assume there exist an optimal arrangement such that the current rectangle[i] is not placed on nested[m] of minimum width that satisfies the above requirement. Suppose rectangle[i] is placed on nested[n], and another rectangle[j] is placed on nested[m] instead. Then since rectangle[j] can fit in nested[n], it can also fit in nested[m], and hence we can swap rectangle[i] and rectangle[j]. By performing the exchange to all such rectangles at all stage, we can transform this optimal arrangement to our greedy arrangement. Hence our greedy arrangement is also optimal.
Inductively, we can prove that the rectangles in nested[i] are always sorted in increasing width.
Lastly, in the case that there is a rectangle with the same heights, we sort the widths in increasing order so as to maintain the sorting order of nested[i].

Below is the implementation of the above approach:

CPP

// CPP program to find the minimum number of rectangles
// left after inserting one into another
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for comparison
bool comp(const pair<int, int>& L, const pair<int, int>& R)
{
    if (L.first == R.first)
        return L.second > R.second;
 
    return L.first < R.first;
}
 
// Function to find the minimum number of rectangles
// left after inserting one into another
int Rectangles(pair<int, int> rectangle[], int n)
{
    // Sort rectangles in increasing order of width
    // and decreasing order of height
    sort(rectangle, rectangle + n, comp);
 
    vector<pair<int, int> > nested;
 
    // Keep the largest rectangle
    nested.push_back(rectangle[n - 1]);
 
    // For all remaining rectangles
    for (int i = n - 2; i >= 0; --i) {
        int high = nested.size() - 1, low = 0;
 
        // Find the position of this rectangle in nested
        while (low <= high) {
            int mid = (high + low) / 2;
            if (nested[mid].first == rectangle[i].first
                || nested[mid].second <= rectangle[i].second)
                low = mid + 1;
 
            else
                high = mid - 1;
        }
 
        // If this rectangle not possible to insert in
        // any other rectangle
        if (low == nested.size())
            nested.push_back(rectangle[i]);
 
        // Replace with previous rectangle
        else {
            nested[low].second = rectangle[i].second;
            nested[low].first = rectangle[i].first;
        }
    }
 
    return ((int)nested.size());
}
 
// Driver code
int main()
{
    // list of Width, Height pair
    pair<int, int> arr[] = { { 20, 30 }, { 10, 10 }, { 30, 20 }, { 40, 50 } };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << Rectangles(arr, n);
 
    return 0;
}

Java

// Java program to find the minimum number of rectangles
// left after inserting one into another
import java.util.*;
class GFG
{
 
  // Function to find the minimum number of rectangles
  // left after inserting one into another
  static int Rectangles(int[][] rectangle, int n)
  {
 
    // Sort rectangles in increasing order of width
    // and decreasing order of height
    Arrays.sort(rectangle, new Comparator<int[] >()
                {
                  public int compare(int[] a, int[] b)
                  {
                    if (a[0] != b[0])
                      return Integer.compare(a[0], b[0]);
                    return Integer.compare(a[1], b[1]);
                  }
                });
 
    ArrayList<ArrayList<Integer>> nested = new ArrayList<ArrayList<Integer>>();
 
    // Keep the largest rectangle
    ArrayList<Integer> l1 = new ArrayList<Integer>();
    for (int i = 0; i < rectangle[n - 1].length; i++)
      l1.add(rectangle[n - 1][i]);
 
    nested.add(l1);
 
    // For all remaining rectangles
    for (int i = n - 2; i >= 0; --i) {
      int high = nested.size() - 1, low = 0;
 
      // Find the position of this rectangle in nested
      while (low <= high) {
        int mid = (int)((high + low) / 2);
        if ((nested.get(mid)).get(0) == rectangle[i][0]
            || (nested.get(mid)).get(1) <= rectangle[i][1])
          low = mid + 1;
 
        else
          high = mid - 1;
      }
 
      // If this rectangle not possible to insert in
      // any other rectangle
      if (low == nested.size())
      {
        ArrayList<Integer> l2 = new ArrayList<Integer>();
        for (int j = 0; j < rectangle[i].length; j++)
          l2.add(rectangle[i][j]);
 
        nested.add(l2);
      }
 
      // Replace with previous rectangle
      else {
        (nested.get(low)).set(1, rectangle[i][1]);
        (nested.get(low)).set(0, rectangle[i][0]);
      }
    }
 
    return nested.size();
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // list of Width, Height pair
    int[][] arr = {  new int [] { 20, 30 },  new int [] {10, 10},  new int [] {30, 20},  new int [] { 40, 50 } };
 
    int n = arr.length;
 
    System.out.println(Rectangles(arr, n));
  }
}
 
// This code is contributed by phasing17

Python3

# Python program to find the minimum number of rectangles
# left after inserting one into another
 
# Function for comparison
from functools import cmp_to_key
 
def comp(L, R):
 
    if (L[0] == R[0]):
        return R[1] - L[1]
 
    return L[0] - R[0]
 
# Function to find the minimum number of rectangles
# left after inserting one into another
def Rectangles(rectangle, n):
 
    # Sort rectangles in increasing order of width
    # and decreasing order of height
    rectangle.sort(key = cmp_to_key(comp))
 
    nested = []
 
    # Keep the largest rectangle
    nested.append(rectangle[n - 1])
 
    # For all remaining rectangles
    for i in range(n - 2,-1,-1):
        high,low = len(nested) - 1,0
 
        # Find the position of this rectangle in nested
        while (low <= high):
            mid = (high + low) // 2
            if (nested[mid][0] == rectangle[i][0] or nested[mid][1] <= rectangle[i][1]):
                low = mid + 1
 
            else:
                high = mid - 1
 
        # If this rectangle not possible to insert in
        # any other rectangle
        if (low == len(nested)):
            nested.append(rectangle[i])
 
        # Replace with previous rectangle
        else:
            nested[low][1] = rectangle[i][1]
            nested[low][0] = rectangle[i][0]
 
    return len(nested)
 
# Driver code
 
# list of Width, Height pair
arr = [ [ 20, 30 ], [ 10, 10 ], [ 30, 20 ], [ 40, 50 ] ]
 
n = len(arr)
 
print(Rectangles(arr, n))
 
# This code is contributed by shinjanpatra

C#

// C# program to find the minimum number of rectangles
// left after inserting one into another
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
   
    // Function to find the minimum number of rectangles
    // left after inserting one into another
    static int Rectangles(int[][] rect, int n)
    {
        // Sort rectangles in increasing order of width
        // and decreasing order of height
        var rectangle = rect.OrderBy(x => x[0])
                              .ThenBy(y => y[1])
                              .ToList();
     
        List<List<int>> nested = new List<List<int>>();
     
        // Keep the largest rectangle
        nested.Add(rectangle[n - 1].ToList());
     
        // For all remaining rectangles
        for (int i = n - 2; i >= 0; --i) {
            int high = nested.Count - 1, low = 0;
     
            // Find the position of this rectangle in nested
            while (low <= high) {
                int mid = (int)((high + low) / 2);
                if (nested[mid][0] == rectangle[i][0]
                    || nested[mid][1] <= rectangle[i][1])
                    low = mid + 1;
     
                else
                    high = mid - 1;
            }
     
            // If this rectangle not possible to insert in
            // any other rectangle
            if (low == nested.Count)
                nested.Add(rectangle[i].ToList());
     
            // Replace with previous rectangle
            else {
                nested[low][1] = rectangle[i][1];
                nested[low][0] = rectangle[i][0];
            }
        }
     
        return nested.Count;
    }
     
    // Driver code
     
    public static void Main(string[] args)
    {
    // list of Width, Height pair
    int[][] arr = {  new int [] { 20, 30 },  new int [] {10, 10},  new int [] {30, 20},  new int [] { 40, 50 } };
     
    int n = arr.Length;
     
    Console.Write(Rectangles(arr, n));
    }
}
 
// This code is contributed by phasing17

Javascript

<script>
 
// JavaScript program to find the minimum number of rectangles
// left after inserting one into another
 
// Function for comparison
function comp(L, R)
{
    if (L[0] == R[0])
        return R[1] - L[1];
 
    return L[0] - R[0];
}
 
// Function to find the minimum number of rectangles
// left after inserting one into another
function Rectangles(rectangle, n)
{
    // Sort rectangles in increasing order of width
    // and decreasing order of height
    rectangle.sort(comp);
 
    let nested = [];
 
    // Keep the largest rectangle
    nested.push(rectangle[n - 1]);
 
    // For all remaining rectangles
    for (let i = n - 2; i >= 0; --i) {
        let high = nested.length - 1, low = 0;
 
        // Find the position of this rectangle in nested
        while (low <= high) {
            let mid = Math.floor((high + low) / 2);
            if (nested[mid][0] == rectangle[i][0]
                || nested[mid][1] <= rectangle[i][1])
                low = mid + 1;
 
            else
                high = mid - 1;
        }
 
        // If this rectangle not possible to insert in
        // any other rectangle
        if (low == nested.length)
            nested.push(rectangle[i]);
 
        // Replace with previous rectangle
        else {
            nested[low][1] = rectangle[i][1];
            nested[low][0] = rectangle[i][0];
        }
    }
 
    return nested.length;
}
 
// Driver code
 
// list of Width, Height pair
let arr = [ [ 20, 30 ], [ 10, 10 ], [ 30, 20 ], [ 40, 50 ] ];
 
let n = arr.length;
 
document.write(Rectangles(arr, n));
 
// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(nlogn)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!