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)