Suma máxima de como máximo dos intervalos que no se superponen en una lista de Intervalos | Problema de programación de intervalos

Dado un intervalo de array de longitud N , donde cada elemento representa tres valores, es decir, {startTime, endTime, value} . La tarea es encontrar la suma máxima de valores de, como máximo, dos intervalos que no se superpongan.

Ejemplo: 

Entrada: intervalo[] = [[1, 3, 2], [4, 5, 2], [2, 4, 3]]
Salida: 4
Explicación: Seleccione el intervalo 1 y 2 (ya que el tercer intervalo se superpone). Por lo tanto, el valor máximo es 2 + 2 = 4.

Entrada: intervalo[] = [[1, 3, 2], [4, 5, 2], [1, 5, 5]]
Salida: 5
Explicación: Como los intervalos 1 y 2 no se superponen, pero su valor será 2 + 2 = 4. Entonces, en lugar de 1 y 2, solo se puede seleccionar 3 con un valor de 5.

Enfoque: este problema se puede resolver con la ayuda de una cola de prioridad . Para resolver este problema, siga los siguientes pasos:

1. Ordene el intervalo de array dado wrt startTime. Si startTime de dos intervalos es el mismo, ordénelo sobre la base de endTime .
2. Almacene el par de {endTime, value} en la cola de prioridad y clasifíquelo según endTime .
3. Recorra la array dada y calcule el valor máximo para todos los eventos cuyo tiempo de finalización sea menor que el tiempo de inicio del intervalo actual y guárdelo en la variable max.
4. Ahora, actualice ans, después de cada recorrido como , ans= Math.max(ans, max + interval[i][2]) .
5. Regresa ans como la respuesta final a este problema.

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

// C++ algorithm for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// maximum value of atmost two
// non-overlapping intervals
int maxTwoNonOverLapping(vector<vector<int> >& interval)
{
   
    // Sorting the given array
    // on the basis of startTime
    sort(interval.begin(), interval.end(),
         [](vector<int>& a, vector<int>& b) {
             return (a[0] == b[0]) ? a[1] < b[1]
                                   : a[0] < b[0];
         });
 
    // Initializing Priority Queue
    // which stores endTime
    // and value and sort
    // on the basis of endTime
    priority_queue<vector<int> > pq;
   
    // Initializing max
    // and ans variables
    int ma = 0;
    int ans = 0;
 
    // Traversing the given array
    for (auto e : interval) {
        while (!pq.empty()) {
 
            // If endTime from priority
            // queue is greater
            // than startTime of
            // traversing interval
            // then break the loop
            if (pq.top()[0] >= e[0])
                break;
            vector<int> qu = pq.top();
            pq.pop();
 
            // Updating max variable
            ma = max(ma, qu[1]);
        }
 
        // Updating ans variable
        ans = max(ans, ma + e[2]);
        pq.push({ e[1], e[2] });
    }
 
    // Returning ans
    return ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > interval
        = { { 1, 3, 2 }, { 4, 5, 2 }, { 1, 5, 5 } };
    int maxValue = maxTwoNonOverLapping(interval);
    cout << maxValue;
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

// Java algorithm for above approach
 
import java.util.*;
 
class GFG {
 
    // Driver Code
    public static void main(String[] args)
    {
        int[][] interval
            = { { 1, 3, 2 }, { 4, 5, 2 }, { 1, 5, 5 } };
        int maxValue = maxTwoNonOverLapping(interval);
        System.out.println(maxValue);
    }
 
    // Function to find
    // maximum value of atmost two
    // non-overlapping intervals
    public static int maxTwoNonOverLapping(int[][] interval)
    {
        // Sorting the given array
        // on the basis of startTime
        Arrays.sort(interval,
                    (a, b)
                        -> (a[0] == b[0]) ? a[1] - b[1]
                                          : a[0] - b[0]);
 
        // Initializing Priority Queue
        // which stores endTime
        // and value and sort
        // on the basis of endTime
        PriorityQueue<int[]> pq
            = new PriorityQueue<>((a, b) -> a[0] - b[0]);
 
        // Initializing max
        // and ans variables
        int max = 0;
        int ans = 0;
 
        // Traversing the given array
        for (int[] e : interval) {
            while (!pq.isEmpty()) {
 
                // If endTime from priority
                // queue is greater
                // than startTime of
                // traversing interval
                // then break the loop
                if (pq.peek()[0] >= e[0])
                    break;
                int[] qu = pq.remove();
 
                // Updating max variable
                max = Math.max(max, qu[1]);
            }
 
            // Updating ans variable
            ans = Math.max(ans, max + e[2]);
            pq.add(new int[] { e[1], e[2] });
        }
 
        // Returning ans
        return ans;
    }
}

## Python program for the above approach:
 
## Function to find
## maximum value of atmost two
## non-overlapping intervals
from queue import PriorityQueue
 
def maxTwoNonOverLapping(interval):
    ## Sorting the given array
    ## on the basis of startTime
    interval.sort()
 
    ## Initializing Priority Queue
    ## which stores endTime
    ## and value and sort
    ## on the basis of endTime
    pq = PriorityQueue()
 
    ## Initializing max
    ## and ans variables
    ma = 0;
    ans = 0
 
    ## Traversing the given array
    for e in interval:
        while not pq.empty():
 
            ## If endTime from priority
            ## queue is greater
            ## than startTime of
            ## traversing interval
            ## then break the loop
            if (pq.queue[0][0] >= e[0]):
                break;
            qu = pq.get();
 
            ## Updating max variable
            ma = max(ma, qu[1]);
 
        ## Updating ans variable
        ans = max(ans, ma + e[2]);
        pq.put([ e[1], e[2] ]);
 
    ## Returning ans
    return ans;
 
## Driver code
if __name__=='__main__':
 
    interval = [ [ 1, 3, 2 ], [ 4, 5, 2 ], [ 1, 5, 5 ] ];
     
    maxValue = maxTwoNonOverLapping(interval);
    print(maxValue);
 
    # This code is contributed by subhamgoyal2014.

5

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)