Maximice el recuento de trillizos crecientes de cualquier permutación de 3 arrays dadas

Dados tres arreglos X[] , Y[] y Z[], cada uno de los cuales consta de N enteros, la tarea es encontrar el número máximo de tripletes (X[i], Y[i], Z[i]) tales que ( X[i] < Y[i] < Z[i]) para cualquier permutación de las tres arrays .

Ejemplos:

Entrada: X = {9, 6, 14, 1, 8}, Y = {2, 10, 3, 12, 11}, Z = {15, 13, 5, 7, 4}
Salida: 3
Explicación:  
Después de reorganizar las arrays X[], Y[] y Z[] como {1, 6, 8, 9, 14}, {3, 2, 10, 12, 11} y {4, 7, 15, 13, 5} respectivamente. Los tripletes crecientes son {1, 3, 4}, {8, 10, 15} y {9, 12, 13}.
Por lo tanto, la cuenta total de tales trillizos es 3.

Entrada: X = {1, 2, 3, 4}, Y = {5, 6, 7, 8}, Z = {9, 10, 11, 12}
Salida: 4

Enfoque ingenuo: el problema dado se puede resolver generando todas las combinaciones posibles de tripletes de las tres arrays y contando esos tripletes que satisfacen las condiciones dadas. Después de comprobar todas las permutaciones, imprima el recuento total de tripletes obtenidos.

Complejidad de Tiempo: O(N*(N!) ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver utilizando el enfoque codicioso , la idea es ordenar la array dada X [] y luego, para encontrar los tripletes, elija aquellos elementos en la array Y [] y Z [] que forman tripletes crecientes para todos los elementos de la array y esta idea se pueden implementar utilizando la cola de prioridad . Siga los pasos a continuación para resolver el problema:

• Ordene la array X[] en orden creciente .
• Inicialice dos colas de prioridad, digamos PQY y PQZ implementando MinHeap para la array Y[] y Z[] respectivamente.
• Almacene todos los elementos de la array Y[] en el PQY .
• Almacene todos los elementos de la array Z[] en el PQZ .
• Atraviese la array X[] y realice los siguientes pasos:
  • Para cada elemento X[i] , saque el elemento de la cola de prioridad PQY hasta que su elemento superior sea más pequeño que X[i] y PQY no esté vacío.
  • Para cada elemento superior del PQY , digamos temp, extraiga el elemento de la cola de prioridad PQZ hasta que su elemento superior sea más pequeño que la temperatura y PQY no esté vacío.
  • Incrementa el valor de count en 1 .
• Después de completar los pasos anteriores, imprima el valor de conteo como el conteo máximo resultante de trillizos.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of triplets
// that are in increasing order from the
// given three arrays after rearranging
int countTriplet(int arr1[], int arr2[],
                 int arr3[], int N)
{
 
    // Sort the given array arr[]
    sort(arr1, arr1 + N);
 
    // Initializing priority queues
    priority_queue<int, vector<int>,
                   greater<int> >
        Y;
    priority_queue<int, vector<int>,
                   greater<int> >
        Z;
 
    // Push array elements arr2[i] in Y
    for (int i = 0; i < N; i++) {
        Y.push(arr2[i]);
    }
 
    // Push array elements arr3[i] in Y
    for (int i = 0; i < N; i++) {
        Z.push(arr3[i]);
    }
 
    int x, y, z;
    int ans = 0;
 
    // Traverse the array arr1[]
    for (int i = 0; i < N; i++) {
 
        x = arr1[i];
        while (!Y.empty()
               && Y.top() <= x)
            Y.pop();
 
        // If Y is empty then there is
        // no more triplets possible
        if (Y.empty())
            break;
 
        y = Y.top();
        Y.pop();
 
        while (!Z.empty()
               && Z.top() <= y)
            Z.pop();
 
        // If Z is empty then there is
        // no more triplets possible
        if (Z.empty())
            break;
 
        z = Z.top();
        Z.pop();
 
        // Increment the triplets count
        ++ans;
    }
 
    // Return the maximum count of triplets
    return ans;
}
 
// Driver Code
int main()
{
    int X[] = { 9, 6, 14, 1, 8 };
    int Y[] = { 2, 10, 3, 12, 11 };
    int Z[] = { 15, 13, 5, 7, 4 };
    int N = sizeof(X) / sizeof(X[0]);
 
    cout << countTriplet(X, Y, Z, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
    // Function to find the number of triplets
    // that are in increasing order from the
    // given three arrays after rearranging
    static int countTriplet(int[] arr1, int[] arr2,
                     int[] arr3, int N)
    {
       
        // Sort the given array arr[]
        Arrays.sort(arr1);
       
        // Initializing priority queues
        Vector<Integer> Y = new Vector<Integer>();
        Vector<Integer> Z = new Vector<Integer>();
       
        // Push array elements arr2[i] in Y
        for (int i = 0; i < N; i++) {
            Y.add(arr2[i]);
        }
        // Push array elements arr3[i] in Y
        for (int i = 0; i < N; i++) {
            Z.add(arr3[i]);
        }
        Collections.sort(Y);
        Collections.sort(Z);
       
        int x, y, z;
        int ans = 0;
       
        // Traverse the array arr1[]
        for (int i = 0; i < N; i++) {
       
            x = arr1[i];
            while (Y.size() > 0 && Y.get(0) <= x)
                Y.remove(0);
       
            // If Y is empty then there is
            // no more triplets possible
            if (Y.size() == 0)
                break;
       
            y = Y.get(0);
            Y.remove(0);
       
            while (Z.size() > 0 && Z.get(0) <= y)
                Z.remove(0);
       
            // If Z is empty then there is
            // no more triplets possible
            if (Z.size() == 0)
                break;
       
            z = Z.get(0);
            Z.remove(0);
       
            // Increment the triplets count
            ++ans;
        }
       
        // Return the maximum count of triplets
        return ans;
    }
     
    public static void main(String[] args) {
        int[] X = { 9, 6, 14, 1, 8 };
        int[] Y = { 2, 10, 3, 12, 11 };
        int[] Z = { 15, 13, 5, 7, 4 };
        int N = X.length;
       
        System.out.println(countTriplet(X, Y, Z, N));
    }
}
 
// This code is contributed by suresh07.

# Python program for the above approach
from queue import PriorityQueue
 
# Function to find the number of triplets
# that are in increasing order from the
# given three arrays after rearranging
def countTriplet(arr1, arr2, arr3, N):
 
    # Sort the given array arr[]
    arr1.sort();
 
    # Initializing priority queues
    Y = PriorityQueue();
    Z = PriorityQueue();
 
    # Push array elements arr2[i] in Y
    for i in range(N):
        Y.put(arr2[i]);
     
 
    # Push array elements arr3[i] in Y
    for i in range(N):
        Z.put(arr3[i]);
 
    x = 0
    y = 0
    z = 0
    ans = 0;
 
    # Traverse the array arr1[]
    for i in range(N):
 
        x = arr1[i];
        while (not Y.empty() and Y.queue[0] <= x):
            Y.get();
 
        # If Y is empty then there is
        # no more triplets possible
        if (Y.empty()):
            break;
 
        y = Y.queue[0];
        Y.get()
 
        while (not Z.empty() and Z.queue[0] <= y):
            Z.get();
 
        # If Z is empty then there is
        # no more triplets possible
        if (Z.empty()):
            break;
 
        z = Z.queue[0];
        Z.get();
 
        # Increment the triplets count
        ans += 1;
 
    # Return the maximum count of triplets
    return ans;
 
# Driver Code
X = [ 9, 6, 14, 1, 8 ];
Y = [ 2, 10, 3, 12, 11 ];
Z = [ 15, 13, 5, 7, 4 ];
N = len(X);
 
print(countTriplet(X, Y, Z, N));
 
# This code is contributed by _saurabh_jaiswal.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to find the number of triplets
    // that are in increasing order from the
    // given three arrays after rearranging
    static int countTriplet(int[] arr1, int[] arr2,
                     int[] arr3, int N)
    {
      
        // Sort the given array arr[]
        Array.Sort(arr1);
      
        // Initializing priority queues
        List<int> Y = new List<int>();
        List<int> Z = new List<int>();
      
        // Push array elements arr2[i] in Y
        for (int i = 0; i < N; i++) {
            Y.Add(arr2[i]);
        }
        // Push array elements arr3[i] in Y
        for (int i = 0; i < N; i++) {
            Z.Add(arr3[i]);
        }
        Y.Sort();
        Z.Sort();
      
        int x, y, z;
        int ans = 0;
      
        // Traverse the array arr1[]
        for (int i = 0; i < N; i++) {
      
            x = arr1[i];
            while (Y.Count > 0
                   && Y[0] <= x)
                Y.RemoveAt(0);
      
            // If Y is empty then there is
            // no more triplets possible
            if (Y.Count == 0)
                break;
      
            y = Y[0];
            Y.RemoveAt(0);
      
            while (Z.Count > 0
                   && Z[0] <= y)
                Z.RemoveAt(0);
      
            // If Z is empty then there is
            // no more triplets possible
            if (Z.Count == 0)
                break;
      
            z = Z[0];
            Z.RemoveAt(0);
      
            // Increment the triplets count
            ++ans;
        }
      
        // Return the maximum count of triplets
        return ans;
    }
 
  static void Main() {
    int[] X = { 9, 6, 14, 1, 8 };
    int[] Y = { 2, 10, 3, 12, 11 };
    int[] Z = { 15, 13, 5, 7, 4 };
    int N = X.Length;
  
    Console.Write(countTriplet(X, Y, Z, N));
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
    // Javascript program for the above approach
     
    // Function to find the number of triplets
    // that are in increasing order from the
    // given three arrays after rearranging
    function countTriplet(arr1, arr2, arr3, N)
    {
       
        // Sort the given array arr[]
        arr1.sort(function(a, b){return a - b});
       
        // Initializing priority queues
        Y = [];
        Z = [];
       
        // Push array elements arr2[i] in Y
        for (let i = 0; i < N; i++) {
            Y.push(arr2[i]);
        }
        // Push array elements arr3[i] in Y
        for (let i = 0; i < N; i++) {
            Z.push(arr3[i]);
        }
        Y.sort(function(a, b){return a - b});
        Z.sort(function(a, b){return a - b});
       
        let x, y, z;
        let ans = 0;
       
        // Traverse the array arr1[]
        for (let i = 0; i < N; i++) {
       
            x = arr1[i];
            while (Y.length > 0 && Y[0] <= x)
                Y.shift();
       
            // If Y is empty then there is
            // no more triplets possible
            if (Y.Count == 0)
                break;
       
            y = Y[0];
            Y.shift();
       
            while (Z.length > 0 && Z[0] <= y)
                Z.shift();
       
            // If Z is empty then there is
            // no more triplets possible
            if (Z.length == 0)
                break;
       
            z = Z[0];
            Z.shift();
       
            // Increment the triplets count
            ++ans;
        }
       
        // Return the maximum count of triplets
        return ans;
    }
     
    X = [ 9, 6, 14, 1, 8 ];
    Y = [ 2, 10, 3, 12, 11 ];
    Z = [ 15, 13, 5, 7, 4 ];
    N = X.length;
   
    document.write(countTriplet(X, Y, Z, N));
     
    // This code is contributed by decode2207.
</script>

3

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)