home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Maximum Length Chain of Pairs

กำหนด Chain of Pairs: แต่ละคู่ (a, b) โดย a < b เสมอ

กฎการต่อยอด: คู่ (x, y) สามารถต่อหลัง (p, q) ได้ก็ต่อเมื่อ q < x

เป้าหมาย: หา ความยาวสูงสุด ของ chain ที่สร้างได้

ตัวอย่าง Input และ Output

Input: {(5, 24), (15, 25), (27, 40), (50, 60)}
Output: Length of maximum size chain is 3
(Chain: (5,24) → (27,40) → (50,60) หรือ (15,25) → (27,40) → (50,60))

อัลกอริทึม Dynamic Programming

ฟังก์ชัน maxChainLength(arr, n)

ขั้นตอน:

  1. Sort คู่ตามค่า a (ตัวแรก) จากน้อยไปมาก
  2. สร้าง maxChainLen[n] เริ่มต้นทุกค่า = 1 (chain ความยาว 1 คือตัวมันเอง)
  3. for i = 1 ถึง n-1:
    • for j = 0 ถึง i-1:
      • ถ้า arr[i].a > arr[j].b และ maxChainLen[i] < maxChainLen[j] + 1
      • → maxChainLen[i] = maxChainLen[j] + 1
  4. คำตอบ = max(maxChainLen[i]) สำหรับทุก i

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

struct numPair {
    int a, b;
};

int maxChainLength(numPair arr[], int n) {
    // เรียงตาม a (ตัวแรก)
    sort(arr, arr+n, [](numPair p1, numPair p2) {
        return p1.a < p2.a;
    });

    int *maxChainLen = new int[n];
    for (int i = 0; i < n; i++) maxChainLen[i] = 1;

    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)
                maxChainLen[i] = maxChainLen[j] + 1;

    int max = 0;
    for (int i = 0; i < n; i++)
        if (max < maxChainLen[i]) max = maxChainLen[i];

    delete[] maxChainLen;
    return max;
}

int main() {
    numPair arr[] = {{5, 24}, {15, 25}, {27, 40}, {50, 60}};
    int n = 4;
    cout << "Length of maximum size chain is " << maxChainLength(arr, n);
    return 0;
}

Output

Length of maximum size chain is 3

ความซับซ้อน

  • Time: O(n²) (หลัง sort O(n log n))
  • Space: O(n)

การเพิ่มประสิทธิภาพ: O(n log n) ด้วย Greedy + Binary Search

คล้าย LIS O(n log n): เก็บ tail ของ chain แต่ละความยาว ใช้ binary search หาตำแหน่งวาง

ความสัมพันธ์กับ LIS

ปัญหานี้เทียบเท่ากับ LIS หากนำคู่ (a,b) มาเรียงตาม a แล้วหา LIS ของ b (แต่เงื่อนไขคือ b[i] < a[j] ไม่ใช่ b[i] < b[j])