Dada una array arr[][] que consta de N listas que representan N transacciones, la tarea es fusionar las listas de transacciones dadas en el orden en que ocurren, de modo que en cualquier momento, la suma de las transacciones ya realizadas no sea negativo. Si se encuentra en negativo, imprima «-1» . De lo contrario, imprima la lista combinada de transacciones.
Ejemplos:
Entrada: arr[][] = {{100 → 400 → -1000 → -500}, {-300 → 2000 → -500}}
Salida: 100 → 400 → -300 → 2000 → -500 → -1000 → -500
Explicación: la suma en cada instante de la lista anterior de transacciones está dada por {100, 500, 200, 2200, 1700, 700, 200}, que no tiene valores negativos.Entrada: arr[][] = [[100 → 400]]
Salida: 100 400
Enfoque: El problema dado se puede visualizar como una variación de fusionar listas enlazadas ordenadas por K con el criterio de que la suma de la lista fusionada de transacciones en cualquier instante no debe ser negativa.
Siga los pasos a continuación para resolver el problema:
- Inicialice un nuevo Node, digamos P , que denota el encabezado de la lista enlazada construida .
- Inicialice una cola de prioridad , digamos PQ , de tamaño N para implementar un Max Heap .
- Inserte las primeras N transacciones como Nodes en PQ .
- Iterar hasta que PQ no esté vacío y realizar los siguientes pasos:
- Extraiga el Node superior de la cola de prioridad e inserte ese Node al final de la lista , con el encabezado P.
- Si existe el siguiente Node del Node emergente, inserte el siguiente Node del Node emergente en PQ .
- Después de completar los pasos anteriores, imprima la lista enlazada formada con el encabezado P .
A continuación se muestra la implementación del enfoque anterior: –
Java
// Java program for the above approach import java.util.*; // Structure of a Node // in the Linked List class Node { int val; Node next; // Constructor Node(int val) { this.val = val; this.next = null; } } class GFG { // Function to merge the Bank sheets public static void mergeSheets( Node lists[]) { // Initialize Max_Heap PriorityQueue<Node> pq = new PriorityQueue<>( new Comparator<Node>() { // Comparator Function // to make it maxHeap public int compare(Node a, Node b) { return b.val - a.val; } }); // Stores the output list Node p, head = new Node(0); p = head; // Insert the first element // of each list for (int i = 0; i < lists.length; i++) { // If the list is not NULL if (lists[i] != null) { // Insert element in // the priority queue pq.add(lists[i]); } } // Iterate until PQ is non-empty while (!pq.isEmpty()) { p.next = pq.poll(); p = p.next; if (p.next != null) pq.add(p.next); } p = head.next; // Print the output list while (p.next != null) { System.out.print(p.val + " "); p = p.next; } System.out.print(p.val); } // Driver Code public static void main(String[] args) { int N = 2; Node arr[] = new Node[N]; arr[0] = new Node(100); arr[0].next = new Node(400); arr[0].next.next = new Node(-1000); arr[0].next.next.next = new Node(-500); arr[1] = new Node(-300); arr[1].next = new Node(2000); arr[1].next.next = new Node(-500); // Function Call mergeSheets(arr); } }
100 400 -300 2000 -500 -1000 -500
Complejidad de tiempo: O(N * log K)
Espacio auxiliar: O(K)