Leetcode – 452. حداقل تعداد فلش برای پشت سر هم بالن

این مشکل ما را ملزم می کند تا حداقل تعداد فلش های مورد نیاز برای ترکیدن همه بادکنک ها را پیدا کنیم ، با توجه به اینکه هر بالون به عنوان یک بازه نشان داده می شود
[start,end]بشر

رویکرد مبتنی بر ایده ادغام فواصل همپوشانی است:

1. اگر دو بادکنک با هم همپوشانی داشته باشند ، می توانند با یک فلش منفرد پشت سر بگذارند.
2. اگر آنها با هم همپوشانی نداشته باشند ، یک فلش جدید لازم است.

برای رسیدن به این هدف ، فواصل را مرتب می کنید و در حالی که می توانید بالن های همپوشانی را ادغام کنید ، از طریق آنها تکرار می کنید.

بالن ها را با موقعیت شروع مرتب کنید

ابتدا آرایه نقاط را به ترتیب صعودی مقادیر شروع مرتب کنید (الف[0] – ب[0]).
این تضمین می کند که ما بادکنک ها را از چپ به راست بر اساس مکان شروع می کنیم.
لیست فواصل ادغام شده (خروجی) را اولیه کنید

با اولین بادکنک به عنوان فاصله اولیه در خروجی شروع کنید.
از طریق بادکنک های مرتب شده تکرار کنید

برای هر بالون در مرتب شده[i]:
همپوشانی را با آخرین بادکنک در خروجی بررسی کنید

• اگر مرتب شود[i][0] <= خروجی[output.length - 1][1]، بالون ها با هم همپوشانی دارند.
• آنها را با به روزرسانی پایان آخرین بازه به Math.min (مرتب سازی شده) ادغام کنید[i][1]، آخرین[1]).
• در صورت عدم همپوشانی ، فاصله جدیدی اضافه کنید
• اگر مرتب شود[i][0] > آخرین[1]، بالون با هم همپوشانی ندارد ، بنابراین ما یک بازه جدید برای خروجی اضافه می کنیم. تعداد فلش ها را برگردانید

اندازه خروجی حداقل تعداد فلش های مورد نیاز را نشان می دهد ، زیرا هر بازه در خروجی با یک شات فلش مطابقت دارد.

• پیچیدگی زمان: 𝑂 (nlog𝑛)
• پیچیدگی فضایی: O (N)

javascript []
/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {

    let sorted = points.sort((a, b) => a[0] - b[0]);
    let output = [sorted[0]];
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i][0] <= output[output.length - 1][1]) { //overlapped
            output[output.length - 1][1] = Math.min(sorted[i][1], output[output.length - 1][1])
        } else {
            output.push(sorted[i]);
        }
    }
    return output.length;

};

راه حل جایگزین

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {
    if (!points.length) return 0;

    // Sort balloons by their end position instead of start position
    let sorted = points.sort((a, b) => a[1] - b[1]);

    let arrows = 1;  // We need at least one arrow
    let prevEnd = sorted[0][1];  // Track the end of the last burst balloon group

    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i][0] > prevEnd) {  // If there's no overlap, fire a new arrow
            arrows++;
            prevEnd = sorted[i][1];  // Update end to current balloon's end
        }
    }

    return arrows;
};