Kth element més petit d'una sèrie d'intervals

Bloc

Kth element més petit d'una sèrie d'intervals

Donat un matriu d’intervals arr [] de mida N , la tasca és trobar el fitxer Kth l'element més petit entre tots els elements dins dels intervals de la matriu donada.



Exemples:

_Introducció: _ arr [] = {{5, 11}, {10, 15}, {12, 20}}, K = 12



_Sortida: _ 13

_Explicació: _ Els elements de la matriu d’intervals donada són: {5, 6, 7, 8, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 17, 18, 19, 20}.



Per tant, l’element més petit de Kth (= 12è) és 13.

_Introducció: _ arr [] = {{5, 11}, {10, 15}, {12, 20}}, K = 7

var fs = require ('fs')

Sortida: 10

Recomanat: proveu el vostre enfocament {AQUÍ} primer, abans de passar a la solució.

** Enfocament ingenu: ** L'enfocament més senzill és generar una nova matriu que consti de tots els elements de la matriu d'intervals. Ordeneu la nova matriu . Finalment, torneu el fitxer Kth element més petit de la matriu .

Complexitat horària: O (X * Log (X)), on ** X ** és el nombre total d'elements en els intervals.

Espai auxiliar: O (registre X * (X))

Enfocament eficient: Per optimitzar l'enfocament anterior, la idea és utilitzar-la MinHeap . Seguiu els passos següents per resoldre el problema.

  1. Crea un MinHeap , digueu ** pq ** per emmagatzemar tots els intervals de la matriu donada de manera que retorni l'element mínim entre tots els elements dels intervals restants a O (1).
  2. Apareix l'interval mínim des del fitxer MinHeap i comproveu si l'element mínim de l'interval emergent és inferior a l'element màxim de l'interval emergent. Si es troba que és cert, inseriu un interval nou {element mínim de l'interval emergent + 1, element màxim de l'interval emergent} .
  3. Repetiu el pas anterior K - 1 vegades.
  4. Finalment, torneu l'element mínim de l'interval emergent.

A continuació es mostra la implementació de l'enfocament anterior:

  • C ++ 14
  • Java

filtre_ninguna

edita

play_arrow

brillantor_4

// C++ Program to implement

// the above approach

#include

**using** **namespace** std;

// Function to get the Kth smallest

// element from an array of intervals

**int** KthSmallestNum(pair<``**int**``, **int**``> arr[],

**int** n, **int** k)

{

// Store all the intervals so that it

// returns the minimum element in O(1)

priority_queue **int**``>,

vector **int**``> >,

greater **int**``> > >

pq;

// Insert all Intervals into the MinHeap

**for** (``**int** i = 0; i

pq.push({ arr[i].first,

arr[i].second });

}

// Stores the count of

// popped elements

**int** cnt = 1;

// Iterate over MinHeap

**while** (cnt

// Stores minimum element

// from all remaining intervals

pair<``**int**``, **int**``> interval

= pq.top();

// Remove minimum element

pq.pop();

// Check if the minimum of the current

// interval is less than the maximum

// of the current interval

**if** (interval.first

// Insert new interval

pq.push(

{ interval.first + 1,

interval.second });

}

cnt++;

}

**return** pq.top().first;

}

// Driver Code

**int** main()

{

// Intervals given

pair<``**int**``, **int**``> arr[]

= { { 5, 11 },

{ 10, 15 },

{ 12, 20 } };

// Size of the arr

**int** n = **sizeof**``(arr) / **sizeof**``(arr[0]);

**int** k = 12;

cout << KthSmallestNum(arr, n, k);

}

#arrays #heap #mathematical #sorting #amazon # amazon-question # min-heap # prioritària-cua

www.geeksforgeeks.org

Kth element més petit d'una sèrie d'intervals

Un portal d’informàtica per a frikis. Conté articles d’informàtica i programació ben escrits, ben pensats i ben explicats, qüestionaris i preguntes sobre pràctiques / programació competitiva / entrevista d’empresa.