Merge Intervals

যেসব time range একে অপরের সাথে overlap করে, সেগুলো মিলিয়ে সবচেয়ে কম সংখ্যক range বানান।

মূল ধারণা (calendar-এর meeting)

আপনার meeting আছে 1–3, 2–6 আর 8–10-এ। প্রথম দুটি overlap করে, তাই আপনার calendar-এ আসলে 1 থেকে 6 পর্যন্ত একটি busy block, আর 8–10। Interval merge করা যেকোনো list-এর জন্য ঠিক এটাই করে।

কৌশলটা হলো আগে start time ধরে sort করা। তাহলে overlap করা range গুলো পাশাপাশি এসে যায়, আর বাঁ থেকে ডানে একবার sweep করলেই যথেষ্ট:

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: সবচেয়ে বেশি খরচ sort করায়, প্রায় n log n ধাপ (O(n log n))। এরপর sweep হলো একবারের pass (O(n))।