Печать цепочки пар максимальной длины

Опубликовано: 20 Января, 2022

Вам даны n пар чисел. В каждой паре первое число всегда меньше второго. Пара (c, d) может следовать за другой парой (a, b), если b <c. Таким образом может быть образована цепочка пар. Найдите самую длинную цепочку, которую можно составить из заданного набора пар.

Примеры:

Ввод: (5, 24), (39, 60), (15, 28), (27, 40), (50, 90).
Выход: (5, 24), (27, 40), (50, 90)

Ввод: (11, 20), {10, 40), (45, 60), (39, 40)
Выход: (11, 20), (39, 40), (45, 60)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

В предыдущем посте мы обсуждали проблему цепочки пар максимальной длины. Тем не менее, сообщение касалось только кода, связанного с поиском длины цепочки максимального размера, но не построения цепочки максимального размера. В этом посте мы обсудим, как построить саму цепочку пар максимальной длины.

Идея состоит в том, чтобы сначала отсортировать заданные пары в порядке возрастания их первого элемента. Пусть arr [0..n-1] будет входным массивом пар после сортировки. Мы определяем вектор L так, что L [i] сам является вектором, который хранит цепочку пар максимальной длины arr [0..i], которая заканчивается на arr [i]. Следовательно, для индекса i L [i] может быть рекурсивно записано как -

L[0] = {arr[0]}
L[i] = {Max(L[j])} + arr[i] where j < i and arr[j].b < arr[i].a 
     = arr[i], if there is no such j

Например, для (5, 24), (39, 60), (15, 28), (27, 40), (50, 90)

L [0]: (5, 24)
L [1]: (5, 24) (39, 60)
L [2]: (15, 28)
L [3]: (5, 24) (27, 40)
L [4]: (5, 24) (27, 40) (50, 90)

Обратите внимание, что сортировка пар выполняется, так как нам нужно найти максимальную длину пары, и порядок здесь не имеет значения. Если мы не сортируем, мы получим пары в порядке возрастания, но это не будут максимально возможные пары.

Below is implementation of above idea –

C++

/* Dynamic Programming solution to construct
   Maximum Length Chain of Pairs */
#include <bits/stdc++.h>
using namespace std;
  
struct Pair
{
    int a;
    int b;
};
  
// comparator function for sort function
int compare(Pair x, Pair y)
{
    return x.a < y.a;
}
  
// Function to construct Maximum Length Chain
// of Pairs
void maxChainLength(vector<Pair> arr)
{
    // Sort by start time
    sort(arr.begin(), arr.end(), compare);
  
    // L[i] stores maximum length of chain of
    // arr[0..i] that ends with arr[i].
    vector<vector<Pair> > L(arr.size());
  
    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);
  
    // start from index 1
    for (int i = 1; i < arr.size(); i++)
    {
        // for every j less than i
        for (int j = 0; j < i; j++)
        {
            // L[i] = {Max(L[j])} + arr[i]
            // where j < i and arr[j].b < arr[i].a
            if ((arr[j].b < arr[i].a) &&
                (L[j].size() > L[i].size()))
                L[i] = L[j];
        }
        L[i].push_back(arr[i]);
    }
  
    // print max length vector
    vector<Pair> maxChain;
    for (vector<Pair> x : L)
        if (x.size() > maxChain.size())
            maxChain = x;
  
    for (Pair pair : maxChain)
        cout << "(" << pair.a << ", "
             << pair.b << ") ";
}
  
// Driver Function
int main()
{
    Pair a[] = {{5, 29}, {39, 40}, {15, 28},
                {27, 40}, {50, 90}};
    int n = sizeof(a)/sizeof(a[0]);
  
    vector<Pair> arr(a, a + n);
  
    maxChainLength(arr);
  
    return 0;
}

Python3

# Dynamic Programming solution to construct
# Maximum Length Chain of Pairs
class Pair:
  
    def __init__(self, a, b):
        self.a = a
        self.b = b
  
    def __lt__(self, other):
        return self.a < other.a
  
def maxChainLength(arr):
      
    # Function to construct
    # Maximum Length Chain of Pairs 
  
    # Sort by start time
    arr.sort()
  
    # L[i] stores maximum length of chain of
    # arr[0..i] that ends with arr[i].
    L = [[] for x in range(len(arr))]
  
    # L[0] is equal to arr[0]
    L[0].append(arr[0])
  
    # start from index 1
    for i in range(1, len(arr)):
  
        # for every j less than i
        for j in range(i):
  
            # L[i] = {Max(L[j])} + arr[i]
            # where j < i and arr[j].b < arr[i].a
            if (arr[j].b < arr[i].a and 
                len(L[j]) > len(L[i])):
                L[i] = L[j]
  
        L[i].append(arr[i])
  
    # print max length vector
    maxChain = []
    for x in L:
        if len(x) > len(maxChain):
            maxChain = x
  
    for pair in maxChain:
        print("({a},{b})".format(a = pair.a, 
                                 b = pair.b), 
                                 end = " ")
    print()
  
# Driver Code
if __name__ == "__main__":
    arr = [Pair(5, 29), Pair(39, 40), 
           Pair(15, 28), Pair(27, 40),
           Pair(50, 90)]
    n = len(arr)
    maxChainLength(arr)
  
# This code is contributed 
# by vibhu4agarwal


Output:
(5, 29) (39, 40) (50, 90)

Временная сложность вышеуказанного решения динамического программирования составляет O (n 2 ), где n - количество пар.
Вспомогательное пространство, используемое программой, равно O (n 2 ).

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ