Encuentra el número mínimo de rectángulos que quedan después de insertar uno en otro

Dado el ancho y la altura de N rectángulos. La tarea es encontrar el número mínimo de rectángulos que quedan después de insertar uno en otro. 
Nota : 
 

1. Si W1 < W2 y H1 < H2, entonces el rectángulo 1 cabe dentro del rectángulo 2.
2. El rectángulo más pequeño puede insertarse en el segundo más pequeño, y este rectángulo puede insertarse en el siguiente y así sucesivamente.

Ejemplos: 
 

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.

Enfoque : 
 

1. En primer lugar, ordene todos los rectángulos de manera que las alturas estén en orden decreciente. Primero supondremos que cada altura es única (luego extenderemos nuestro enfoque al caso donde hay las mismas alturas).
2. Mantenemos otra array nested[i]. Comenzando desde el rectángulo más alto hasta el más bajo, intentaremos encajar en el rectángulo anidado[i], encontrando un rectángulo anidado en anidado[i] en el que su ancho sea mayor que el de nuestro rectángulo actual. No solo eso, queremos colocarlo en el que tenga el ancho mínimo. Luego colocamos el rectángulo dentro de ese rectángulo anidado y actualizamos su nueva altura y peso. ¿Por qué el mínimo? Porque si colocamos el rectángulo sobre otro con un ancho mayor que el ancho mínimo, podemos aplicar el siguiente argumento de intercambio: 
   Supongamos que existe una disposición óptima tal que el rectángulo actual [i] no se coloca en un [m] anidado de ancho mínimo que satisfaga el requisito anterior. Supongamos que el rectángulo[i] se coloca en nested[n] y, en su lugar, se coloca otro rectángulo[j] en nested[m]. Entonces, dado que el rectángulo [j] puede caber en anidado [n], también puede caber en anidado [m] y, por lo tanto, podemos intercambiar rectángulo [i] y rectángulo [j]. Al realizar el intercambio de todos estos rectángulos en todas las etapas, podemos transformar este arreglo óptimo en nuestro arreglo codicioso. Por lo tanto, nuestro arreglo codicioso también es óptimo.
3. Inductivamente, podemos probar que los rectángulos en nested[i] siempre se ordenan en anchura creciente.
4. Por último, en el caso de que haya un rectángulo con las mismas alturas, ordenamos los anchos en orden creciente para mantener el orden de clasificación de nested[i].

A continuación se muestra la implementación del enfoque anterior: 
 

// 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;
}

# 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

<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>

2

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar: O(n)