Encuentre una string binaria de longitud N que tenga la suma máxima de elementos de rangos dados

Dada una array de pares rangos[] de tamaño M y un número entero N , la tarea es encontrar una string binaria de longitud N tal que la suma de los elementos de la string de los rangos dados sea la máxima posible.

Ejemplos: 
 

Entrada: N = 5, M = 3, rangos[] = {{1, 3}, {2, 4}, {2, 5}}
Salida: 01100
Explicación:
Rango [1, 3]: Frecuencia de 0 = 1 , Frecuencia de 1 = 2. Suma = 1*2 = 2
Rango [2, 4]: Frecuencia de 0 = 1, Frecuencia de 1 = 2. Suma = 1*2 = 2
Rango [2, 5]: Frecuencia de 0 = 2, Frecuencia de 1 = 2. Suma = 2*2 = 4
Por lo tanto, la suma requerida = 2 + 2 + 4 = 8, que es la máxima posible.

Entrada: N = 6, M = 1, rangos = {{1, 6}}
Salida: 000111

Enfoque: El problema dado se puede resolver encontrando la diferencia absoluta entre el conteo de 0 y el conteo de 1 lo más pequeño posible para cada rango. Por lo tanto, la idea es colocar ambos, es decir, 0 y 1 en una frecuencia casi igual en la string . La mejor forma de hacerlo es colocando los 0 y los 1 alternativamente.

Por lo tanto, a partir de las observaciones anteriores, para generar la string resultante, la idea es iterar sobre el rango [1, N] usando la variable i y si el valor de i es impar, entonces imprima 0, de lo contrario imprima 1 .

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 an N-length binary
// string having maximum sum of
// elements from all given ranges
void printBinaryString(int arr[][3], int N)
{
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // If i is odd, then print 0
        if (i % 2) {
            cout << 0;
        }
 
        // Otherwise, print 1
        else {
            cout << 1;
        }
    }
}
 
// Driver Code
int main()
{
    int N = 5, M = 3;
    int arr[][3] = { { 1, 3 },
                     { 2, 4 },
                     { 2, 5 } };
 
    // Function Call
    printBinaryString(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to find an N-length binary
// string having maximum sum of
// elements from all given ranges
static void printBinaryString(int arr[][], int N)
{
   
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // If i is odd, then print 0
        if (i % 2 == 1) {
             System.out.print(0);
        }
 
        // Otherwise, print 1
        else {
            System.out.print(1);
        }
    }
}
 
// Driver Code
    public static void main (String[] args) {
        int N = 5, M = 3;
    int arr[][] = { { 1, 3 },
                     { 2, 4 },
                     { 2, 5 } };
 
    // Function Call
    printBinaryString(arr, N);
    }
}
 
// This code is contributed by Lokeshpotta20.

# Python program for the above approach
 
# Function to find an N-length binary
# string having maximum sum of
# elements from all given ranges
def printBinaryString(arr, N):
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
 
        # If i is odd, then print 0
        if (i % 2):
            print(0, end="");
 
        # Otherwise, print 1
        else:
            print(1, end="");
 
 
# Driver Code
N = 5;
M = 3;
arr = [ [ 1, 3 ], [ 2, 4 ], [ 2, 5 ] ];
 
# Function Call
printBinaryString(arr, 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 an N-length binary
// string having maximum sum of
// elements from all given ranges
static void printBinaryString(int [,]arr, int N)
{
   
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // If i is odd, then print 0
        if (i % 2 == 1) {
           Console.Write(0);
        }
 
        // Otherwise, print 1
        else {
            Console.Write(1);
        }
    }
}
 
// Driver Code
public static void Main()
{
    int N = 5;
    int [,]arr = { { 1, 3 },
                     { 2, 4 },
                     { 2, 5 } };
 
    // Function Call
    printBinaryString(arr, N);
}
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript program for the above approach
 
// Function to find an N-length binary
// string having maximum sum of
// elements from all given ranges
function printBinaryString(arr, N)
{
    // Iterate over the range [1, N]
    for (let i = 1; i <= N; i++) {
 
        // If i is odd, then print 0
        if (i % 2) {
            document.write(0);
        }
 
        // Otherwise, print 1
        else {
            document.write(1);
        }
    }
}
 
// Driver Code
    let N = 5, M = 3;
    let arr = [ [ 1, 3 ],
                     [ 2, 4 ],
                     [ 2, 5 ] ];
 
    // Function Call
    printBinaryString(arr, N);
 
// This code is contributed by subhammahato348.
</script>

01010

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