اَلگونَوَردی ۲: بازه ها را با هم ترکیب کنید! (حل شد توسط alireza.sharifianzadeh)

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

سوال: تعدادی بازه داده شده اند. بازه هایی که همپوشانی دارند را ترکیب کنید.

مثال: اگر بازه های [5, 3] و [6, 4] و [0, 2-] داده شده باشند، برنامه باید [6, 3] و [0, 2-] را برگرداند.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 6 آوریل

یادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.

توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.

حل مساله

الگونورد برتر: الگونورد برتر الگونورد ۲، کاربر با ای دی alireza.sharifianzadeh هست.

ایشون درست و کامل مساله را حل کردن و خلاصه راه حل رو نوشتند. تشریح حل مساله رو من در نقاط بسیاری ویرایش کردم.

به alireza.sharifianzadeh تبریک می گم و بهش می گم: خیلی خوبی! ادامه بده!

و حالا شرح پاسخ:

پاسخ: حل مسئله با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را فهمیده ایم. مثلا اگر سه بازه [5, 3] و [6, 4] و [0, 2-] داده شده باشند، آنگاه بازه های [5, 3] و [4, 6] که همپوشانی دارند را باید با هم ترکیب کنیم تا بازه جدید [6, 3] بوجود آید. از آنجا که این بازه جدید و بازه [0, 2-] همپوشانی ندارند نمی توانند با هم ترکیب شوند.  نهایتا برنامه باید [6, 3] و [0, 2-] را برگرداند.

ارائه راه حل را از روش جستجوی کامل شروع می کنیم. در این روش هر بازه را به بازه های دیگر مقایسه می کنیم و اگر همپوشانی دارند آنها را با هم ترکیب کرده و یک بازه جدید ایجاد می کنیم. این بازه جدید را جایگزین دو بازه های که آن را بوجود آورده اند می کنیم. بنابر این برای هر بازه باید همپوشانی آن با تمام بازه های دیگر را بررسی کنیم. این کار با استفاده از دو حلقه تو در تو قابل انجام است، به این صورت که حلقه ی بیرونی، عناصر را پیمایش می‌کنه و حلقه داخلی عنصر جاری رو با بازه های دیگر مقایسه می‌کنه و درصورت امکان آنها را با هم ترکیب می کند . پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد.

اشکال این روش آن است که همه بازه هایی نمی توانند با هم ترکیب شوند را نیز با هم مقایسه می کند. همچنین، نمی تواند یک بازه را بصورت کامل و تنها با یک پیمایش بسازد. به عنوان مثال اگر بازه های [6, 3] [4, 0] [7, 5] را از چپ به راست در نظر بگیریم و شروع به ترکیب بازه ها کنیم، آنگاه در نگاه اول بازه [7, 5] و [4, 0] با هم ترکیب نمی شوند. اما وقتی که ]7, 5] را با [6, 3] را با هم ترکیب کنیم و به بازه [7, 3] برسیم. تنها در دور ترکیب بازه هاست که متوجه می شویم که [4, 0] هم می توانست با این دو بازه ترکیب شود و بازه نهایی [7, 0] را بوجود آورد. تامل در این نکته که چرا ترکیب برای بازه اول و سوم اتفاق افتاد اما برای بار دوم اتفاق نیفتاد کلید ارائه یک الگوریتم با سرعت بالاتر است.

در واقع اگر این سه بازه بصورت [7, 5] [6, 3]  [4, 0] بودند آنگاه تنها یک دور پیمایش لیست بازه ها برای تشکیل بازه های ترکیبی جدید کافی بود. این برای هر تعداد بازه متوالی که بر اساس مقدار شروع بازه مرتب شده باشند صادق است.

در واقع چنانچه قبل از انجام عملیات ترکیب، بازه ها را  بر اساس مقدار شروع بازه ( start) مرتب کنیم، دیگر لازم نیست هر بازه با همه ی بازه های دیگه مقایسه کنیم زیرا:

• مقدار end هر بازه از مقدار start در همون بازه بزرگتر است
• مقدار start هر بازه از مقدار start بازه ی قبلی قطعا بزرگتر است

درنتیجه قطعا مقدار end هر بازه از مقدار start بازه قبلی کوچکتر است و می توانیم به این نتیجه برسیم که در صورت مرتب بودن بازه ها، اگر بازه ای با بازه ی بعدی خودش هم پوشانی نداشت، قطعا با بازه های بعد تراز اون نیز هم پوشانی نخواهد داشت.

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

current.start <= prev.end

با این ترتیب شروع به نوشتن برنامه می کنیم و همزمان خطوط برنامه را توضیح می دهیم. ابتدا لیست رو بر اساس مقدار start هر بازه مرتب می‌کنیم (خط 2).  سپس یک لیست خالی (result) برای بازه های ترکیب شده در نظر میگیریم (خط 3). در یک حلقه تکرار هر عنصر را با آخرین عنصر لیست بازه های ترکیبی (list) مقایسه می‌کنیم. در صورتی که عنصر کنونی با آخرین عنصر لیست بازه های ترکیبی همپوشانی داشته باشد، آندو را با بروز رسانی انتهای آخرین بازه ترکیبی، با هم ترکیب می کنیم (خط 5 و 6).

چون عنصر اول لازم نیست با عنصر قبلی مقایسه شود مستقیما داخل result قرار می‌گیرد.

و در صورتی که هم پوشانی وجود نداشته باشد، به این معناست که این عنصر با هیچ عنصر دیگه ای در آرایه همپوشانی نداره، پس این عنصر رو به پاسخ اضافه می‌کنیم (خط 8). در انتهای لیست ترکیبی جدید را به عنوان پاسخ برمی گردانیم.

الگوریتم فوق دارای یک حلقه تکرار است که تنها یک بار عناصر لیست را پیمایش می کند. یک اشتباه رایج آن است که پیچیدگی محاسباتی این الگوریتم را (O(n ارزیابی نماییم. اما نکته مهم آن است که ابتدا باید لیست را مرتب نماییم که خود دارای پیچیدگی محاسباتی ((O(n*log(n می باشد. بنابر این پیچیدگی محاسباتی الگوریتم نیز ((O(n*log(n می باشد.

یک پیاده سازی دیگر این الگوریتم که با توضیح روش مرتب کن و ترکیب کن سازگارتر است در زیر ارایه شده است. حلقه داخلی (خط 7 تا 10) تا جایی ادامه می یابد که دنباله ای از همه بازه های قابل ترکیب را با هم ترکیب کند و یک بازه جدید ترکیبی بسازد.