Combinar transacciones en hojas de banco en el orden en que ocurren, de modo que su suma siga siendo positiva

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:

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);
    }
}
Producción: 

100 400 -300 2000 -500 -1000 -500

 

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

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *