Sorting و Intervalsmerge sort · quicksort · comparators · counting sort · intervals · sweep line

الـ sort هو أشهر preprocessing step في الانترفيو: ترتّب الأول، والمسألة اللي كانت O(n²) تبقى loop واحدة. هتفهم الـ sort شغال إزاي من جوه، وتكتب أي comparator في JS صح، وبعدين تستخدمه في عيلة كاملة من المسائل: الـ intervals.

قبله: Two Pointers و Prefix Sum بيمهّد لـ: Binary Search و Greedy

هتطلع من الفصل ده وإنت عارف

  • تكتب merge sort من دماغك، وتعرف ليه <= في الـ merge هي اللي بتخلّيه stable.
  • تعرف ليه مفيش comparison sort أسرع من O(n log n)، وإمتى counting sort يكسر القاعدة دي.
  • تكتب أي comparator في JS: تصاعدي، تنازلي، multi-key، strings، وتتجنب فخ الـ sort() الفاضية.
  • تحل 6 مسائل intervals، وتعرف إمتى ترتّب بالـ start وإمتى بالـ end، وإمتى الشرط <= وإمتى <.

ليه نفهم الـ sort من جوه؟

في الفصل اللي فات (Prefix Sum) خلصنا الـ arrays، وآخر حاجة وعدناك بيها إن الـ +1 و -1 على timeline بيعدّوا الـ meetings الشغالة. وقبلها في Two Pointers كتبت nums.sort((a, b) => a - b) في أول سطر من 3Sum وكمّلت من غير ما تسأل. دلوقتي هنفتح الـ sort ده من جوه، وبعدين نستخدمه في الـ intervals ونوفي بالوعد.

طب ليه تفهم الـ sort وإنت عمرك ما هتكتبه في الانترفيو؟ عشان:

الطريقة البديهية اللي أي حد بيرتّب بيها: دوّر على أصغر رقم وحطه في الأول، وبعدين أصغر رقم في الباقي، وهكذا. اسمها selection sort:

عدّ معاه المقارنات على 6 أرقام بس:

15 مقارنة على 6 أرقام، يعني n(n - 1) / 2، يعني O(n²). على n = 100,000 ده 5 مليار مقارنة، يعني TLE. الـ merge sort هيعملها في حوالي 1.7 مليون.

تشبيه في كنترول الثانوية العامة عندك 64 ورقة إجابة عايز ترتّبها برقم الجلوس. بدل ما تدوّر على أصغر رقم 64 مرة، تقسم الكومة على اتنين زمايلك، وكل واحد يقسم كومته تاني، لحد ما كل واحد معاه ورقة واحدة (ودي مترتبة لوحدها). بعدين كل اتنين يدمجوا كومتين مترتبتين: يبصوا على أول ورقة في الكومتين وياخدوا الأصغر. ده merge sort.

بس قبل ما نشوف إزاي الـ sort بيشتغل، إمتى أصلًا تفكّر إنك ترتّب؟

إمتى ترتّب؟ وإزاي تعرف مسألة intervals

لما تشوف: intervalsmeetings / scheduleoverlapmerge max non-overlappingmin rooms / at the same timek-th smallest duplicatespairs by value (not index)custom order
ومش sort غالبًا لو: return original indicescontiguous subarrayalready sortedmust be O(n)

الـ sort بيبوّظ الترتيب الأصلي، فلو المطلوب indices أو subarray متصلة، الترتيب بيضيّع المعلومة اللي محتاجها. ولو الـ array مترتبة أصلًا، يبقى المطلوب غالبًا binary search أو two pointers.

في الـ intervals بالذات، فيه 4 أنواع، وكل نوع ليه ترتيب وشرط:

النوعترتّب بإيهالقرارمسائل
ادمج المتداخلstartstart <= lastEnd يبقى ادمج56، 57
أكبر عدد مش متداخل / أقل حذفendstart >= lastEnd يبقى خده435، 452
تقاطع قايمتين مترتبتينمترتبين جاهزtwo pointers: max(starts) <= min(ends)986
كام واحد في نفس اللحظةevents+1 عند البداية و -1 عند النهاية1094، 2406
flowchart TD
  A["Intervals problem"] --> B{"Two lists, each already sorted?"}
  B -- yes --> T["Two pointers: 986"]
  B -- no --> C{"How many at the same moment?"}
  C -- yes --> S["Sweep line: +1 at start, -1 at end"]
  C -- no --> D{"Keep max non-overlapping / min removals / arrows?"}
  D -- yes --> E["Sort by END, greedy"]
  D -- no --> M["Sort by START, merge with the last one"]
  

اسأل الأسئلة دي بالترتيب ده. هنرجعلها بالتفصيل في جزء الـ intervals.

طب الـ sort اللي هنعتمد عليه في كل ده، بيرتّب في O(n log n) إزاي؟

Merge Sort: قسّم، رتّب، ادمج

الفكرة كلها 3 خطوات:

  1. لو الـ array فيها عنصر واحد أو فاضية، هي مترتبة أصلًا. ده الـ base case.
  2. غير كده، قسّمها نصين، ورتّب كل نص بنفس الدالة.
  3. ادمج النصين المترتبين في array واحدة مترتبة.

الدالة بتنادي نفسها، وده اسمه recursion، وليه فصل كامل (Recursion). هنا كفاية تثق إن "رتّب النص" بيرجّعلك نص مترتب. الشغل الحقيقي كله في الـ merge.

  1. ليه <= 1 مش === 1؟ عشان الـ input نفسه ممكن يبقى فاضي. ومن غير base case خالص، array فيها عنصر واحد هتتقسم لـ [] ونفس العنصر، فهتنادي نفسك على نفس الحجم للأبد: Maximum call stack size exceeded.
  2. الـ Math.floor لأن القسمة في JS مش بتقطع زي C++: 5 / 2 = 2.5، ومفيش index اسمه 2.5. مع 5 عناصر، الشمال 2 واليمين 3.
  3. الـ slice(0, mid) بياخد من 0 لحد mid - 1، لأن الـ end في slice exclusive.
  4. الـ slice(mid) من mid للآخر. الاتنين مع بعض بيغطّوا كل عنصر مرة واحدة بالظبط. لو كتبت slice(mid + 1) هتضيّع arr[mid].
  5. هنا النصين مترتبين، فاضل ندمجهم.
  6. i و j بيشاوروا على أول عنصر لسه ما اتاخدش في كل نص. ده نفس الـ two pointers، بس كل pointer في array لوحده.
  7. && مش ||: بنقارن بس طول ما الاتنين فيهم عناصر. مع ||، لو b خلص هتقارن a[i] <= undefined، وده false، فهتعمل push لـ undefined للأبد. infinite loop.
  8. الـ key line. خد الأصغر. وليه <= مش <؟ لو متساويين بناخد من a الأول، و a هو النص الشمال، يعني العناصر اللي كانت قبل في الأصل. كده المتساويين بيفضلوا بترتيبهم الأصلي، وده اسمه stable. مع < الترتيب هيطلع صح برضه، بس مش stable.
  9. لما واحد يخلص، الباقي في التاني مترتب وكله أكبر من أي حاجة في out، فبنلزقه زي ما هو. واحدة بس من الـ loops دي هي اللي هتلف فعلًا، بس إحنا مش عارفين أنهي واحد خلص، فبنكتب الاتنين.
  10. بنرجّع array جديدة. يعني merge sort بالشكل ده محتاج O(n) memory زيادة.

الصورة الكبيرة: split وبعدين merge

الـ range الملوّن هو الجزء اللي الدالة شغالة عليه دلوقتي، والـ call stack تحت بيوريك مين مستني مين:

آخر merge في الـ animation دي بيدمج [2, 4, 5, 7] مع [1, 2, 3, 6]. خلينا نشوفه بالبطيء، مقارنة مقارنة:

ليه O(n log n)؟

كل مرة بنقسم على 2، فعدد المستويات log₂ n (8 عناصر: 3 مستويات). وفي كل مستوى، الـ merges كلها مع بعض بتلمس كل عنصر مرة واحدة، يعني n شغل. المجموع n × log n، وده في كل الحالات، حتى لو الـ input مترتب أو معكوس. والـ memory O(n) عشان الـ arrays الجديدة.

لو غيّرت a[i] <= b[j] لـ a[i] < b[j] في الـ merge، إيه اللي هيحصل؟

  • الـ array مش هتترتب صح
  • infinite loop
  • هتترتب صح، بس المتساويين ممكن يتبدّلوا، فالـ sort مش هيبقى stable
  • مفيش أي فرق خالص

لما a[i] === b[j]، مع < هياخد من b الأول. الأرقام هتطلع مترتبة، بس لو بترتّب objects بـ key، الـ object اللي كان بعد هيعدّي اللي كان قبله.

الـ merge sort ثابت O(n log n) بس بياكل memory. فيه sort تاني بيرتّب in-place، وهو اللي أغلب المكتبات القديمة بنيت عليه. إزاي؟

Quicksort: فكرة الـ partition

الـ key insight: اختار عنصر اسمه pivot، وحط كل اللي أصغر منه على شماله وكل اللي أكبر على يمينه. كده الـ pivot وقف في مكانه النهائي بالظبط، ومش هيتحرك تاني. بعدين كرر نفس الكلام على الشمال لوحده واليمين لوحده.

الـ partition بطريقة Lomuto هو نفس قالب read و write اللي في Two Pointers: j بيقرا كل عنصر، و i هو المكان اللي هيتحط فيه الصغير الجاي.

  1. الـ pivot هو آخر عنصر. سهل، بس هنشوف تحت إنه خطر على array مترتبة.
  2. الـ small zone هي [lo .. i - 1]، وفي الأول فاضية، فـ i = lo. ده بالظبط write في قالب two pointers.
  3. j < hi مش <= hi، لأن nums[hi] هو الـ pivot نفسه، ومكانه بيتحدد في الآخر.
  4. لقينا رقم أصغر، فبنعمل swap مع أول خانة بعد الـ small zone وبنكبّرها. swap مش copy، عشان اللي كان عند i رقم كبير، وما ينفعش يضيع.
  5. كل اللي قبل i أصغر من الـ pivot، وكل اللي من i لـ hi - 1 أكبر أو يساوي. فمكان الـ pivot الصح هو i بالظبط.
  6. >= مش ===: لو الـ pivot وقف عند lo، النداء quickSort(lo, p - 1) بيبقى range فاضي فيه lo > hi.
  7. p - 1 و p + 1 لأن الـ pivot خلص. لو دخّلته تاني في الـ range، ممكن تنادي على نفس الـ range للأبد (لو الـ pivot كان أكبر واحد، quickSort(lo, p) هو نفس quickSort(lo, hi)).

الـ complexity: في المتوسط الـ pivot بيقسم كويس، فـ O(n log n) ومن غير memory زيادة غير الـ recursion. بس لو الـ array مترتبة أصلًا والـ pivot آخر عنصر، كل partition بيشيل عنصر واحد بس: n + (n-1) + … + 1، يعني O(n²). الحل: اختار pivot عشوائي (اعمل swap لعنصر random مع nums[hi] قبل الـ partition). وخلي بالك إن quicksort مش stable، لأن الـ swap بيرمي عناصر فوق عناصر مساوية ليها.

Merge sortQuicksortJS sort (V8: TimSort)Counting sort
TimeO(n log n) دايمًاO(n log n) average، O(n²) worstO(n log n)، و O(n) لو شبه مترتبةO(n + k)
MemoryO(n)O(log n)O(n)O(k)
Stableآهلأآه، مضمون من ES2019آه

الاتنين O(n log n). طب ليه ما حدّش لقى sort أسرع من كده؟

ليه مفيش comparison sort أسرع من O(n log n)؟

أي sort بالمقارنة بيتعلم عن الـ array بسؤال واحد بس: "الـ a أصغر من الـ b؟"، والإجابة آه أو لأ. مع n عنصر فيه n! ترتيب ممكن للـ input، والـ algorithm لازم يفرّق بينهم كلهم، لأن كل ترتيب محتاج حركات مختلفة عشان يتصلّح.

كل سؤال آه/لأ بيقسم الاحتمالات لمجموعتين في أحسن الأحوال. فبعد k سؤال، أقصى حاجة تفرّق بين 2k حالة. محتاج 2k ≥ n!، يعني k ≥ log₂(n!)، والرقم ده تقريبًا n log₂ n.

مثال: 3 عناصر ليهم 3! = 6 ترتيبات. سؤالين بيفرّقوا بين 4 بس، فلازم 3 أسئلة في الـ worst case. ده الـ decision tree:

flowchart TD
  Q1{"a smaller than b?"} -- yes --> Q2{"b smaller than c?"}
  Q1 -- no --> Q4{"a smaller than c?"}
  Q2 -- yes --> L1["a, b, c"]
  Q2 -- no --> Q3{"a smaller than c?"}
  Q3 -- yes --> L2["a, c, b"]
  Q3 -- no --> L3["c, a, b"]
  Q4 -- yes --> L4["b, a, c"]
  Q4 -- no --> Q5{"b smaller than c?"}
  Q5 -- yes --> L5["b, c, a"]
  Q5 -- no --> L6["c, b, a"]
  

6 ورقات (ترتيبات)، وأطول طريق فيه 3 أسئلة. مفيش tree بعمق 2 تقدر تشيل 6 ورقات.

nأقل عدد مقارنات log₂(n!)n log₂ nn²
32.6 → 34.89
815.3 → 162464
1,000~8,530~9,9661,000,000
100,000~1.52M~1.66M10,000M
الـ takeaway العملي لو المسألة عايزة O(n) والحل بتاعك فيه sort، يبقى محتاج فكرة تانية: hash map، أو counting sort لو الأرقام في range صغير.

يعني الـ sort أصلًا أبطأ من O(n). طب لما بتستخدم الـ built-in، فيه حاجة تانية لازم تعرفها: لو عنصرين متساويين، مين يطلع الأول؟

Stability: ترتيب المتساويين

الـ sort يبقى stable لو العناصر المتساوية (حسب الـ comparator) فضلت بنفس ترتيبها الأصلي. مع أرقام لوحدها مش فارقة، 5 زي 5. بس مع objects فارقة جدًا:

تشبيه طابور البنك بالأولوية: كبار السن الأول. لو اتنين كبار سن، اللي جه الأول يفضل الأول. لو الموظف بدّلهم، الترتيب بالأولوية لسه "صح"، بس ظلم اللي جه بدري. الـ stable sort هو الموظف اللي ما بيظلمش.

الـ stability جاية منين في الكود؟ في الـ merge من <=، وهتشوفها في الجزء الجاي في insertion sort من > 0. والجزء الجاي هو الأهم عمليًا: إزاي تقول للـ sort "رتّب بالطريقة دي".

الـ comparator في JS بالتفصيل

الفخ الأول: sort() من غير comparator بيحوّل كل حاجة لـ string ويقارن حرف حرف:

العقد بتاع الـ comparator: cmp(a, b) بيرجّع رقم:

كل الأشكال اللي هتحتاجها في الانترفيو في مكان واحد:

  1. لو a = 2 و b = 10، a - b = -8 سالب، فالـ 2 قبل الـ 10. ده ascending. وفي JS الأرقام doubles، فـ a - b مش بيعمل overflow حتى مع أرقام قريبة من 2³¹، عكس int في C++.
  2. عكس الطرح يعكس الترتيب. بلاش sort(a - b).reverse(): شغل زيادة، وبيعكس ترتيب المتساويين فبيبوّظ الـ stability.
  3. بالـ start بس. الـ intervals اللي ليها نفس الـ start بتفضل بترتيبها الأصلي.
  4. الـ multi-key trick: لو a[0] - b[0] طلع 0، والـ 0 falsy، فالـ || بيروح للـ key التاني. لو مش صفر، هو الإجابة على طول.
  5. الـ key التاني معكوس: start تصاعدي، ولو الـ start واحد، الأطول الأول. هتحتاجه في التمرين آخر الفصل.
  6. آمن بس مع كلمات lowercase. الحروف الكبيرة كلها قبل الصغيرة ('Z' كوده 90 و 'a' كوده 97)، فـ ['b', 'A', 'a', 'B'] بتطلع ['A', 'B', 'a', 'b'].
  7. الـ localeCompare بيرتّب زي القاموس: ['a', 'A', 'b', 'B']، وبيرجّع رقم سالب أو صفر أو موجب. أبطأ شوية، استخدمه لما الكلام عن أسامي ناس.
  8. نفس ترتيب الـ default، بس كـ رقم، فتقدر تحطه جوه comparator بأكتر من key.
  9. بالطول الأول، ولو الطول واحد بالترتيب الأبجدي.
  10. objects: الـ score تنازلي، ولو متساوي الاسم تصاعدي.
  11. Bug مشهور: a > b بيرجّع true أو false، يعني 1 أو 0، عمره ما بيرجّع سالب. في Node الحالي [5, 1, 4, 2, 3].sort((a, b) => a > b) بترجع [5, 1, 4, 2, 3] زي ما هي من غير أي error.

الـ comparator بيتسأل إمتى؟

عشان تشوف بعينك، هنستخدم insertion sort بسيط بياخد comparator. الـ JS الحقيقي بيستخدم TimSort، وهو أصلًا بيعمل insertion sort على الأجزاء الصغيرة، فبيسأل الـ comparator نفس السؤال: "arr[j] المفروض ييجي بعد x؟".

  1. الـ invariant: arr[0 .. i - 1] مترتب. عنصر واحد مترتب لوحده، فنبدأ من i = 1.
  2. بنحفظ x في متغير لأن الـ shift هيكتب فوق arr[i].
  3. j >= 0 الأول عشان الـ short-circuit يحمينا من arr[-1]. و > 0 مش >= 0: لو الـ comparator قال صفر (متساويين) نقف، فـ x يفضل بعد المساوي ليه. ده اللي بيخلّيه stable.
  4. نزق العنصر الأكبر خطوة يمين عشان نفضّي مكان.
  5. j + 1 لأن الـ loop وقفت عند عنصر مكانه قبل x (أو عند -1)، فـ x مكانه بعده على طول.

شوف (a, b) => a[0] - b[0] || a[1] - b[1] وهو بيقرر. الـ cmp في الـ vars هو اللي رجع من الـ comparator:

Insertion sort نفسه O(n²) في الـ worst case، بس O(n) على array شبه مترتبة، وعشان كده TimSort بيستخدمه على الأجزاء الصغيرة.

sort بيعدّل الـ array نفسها const s = nums.sort(...) بيرتّب nums نفسها، و s هو نفس الـ reference. لو محتاج الأصل، اعمل [...nums].sort(...) أو nums.toSorted(...) (Node 20+).

كل ده comparison sort، يعني مش هينزل تحت O(n log n). طب لو الأرقام كلها بين 0 و 100، نقدر نرتّب من غير ما نقارن خالص؟

Counting Sort: لما الأرقام في range صغير

لو الأرقام integers بين 0 و k والـ k صغير (درجات من 0 لـ 100، أعمار، حروف a لـ z، ألوان 0 و 1 و 2)، ما تقارنش خالص: عدّ كل رقم ظهر كام مرة، وبعدين اكتبهم بالترتيب. ده O(n + k)، ومش بيكسر قاعدة الـ n log n لأنه مش بيقارن أصلًا، بيستخدم الرقم نفسه كـ index.

  1. maxVal + 1 لأن القيم من 0 لـ maxVal، يعني maxVal + 1 قيمة. والـ fill(0) ضروري: new Array(n) لوحدها خانات فاضية، و undefined + 1 بيطلع NaN.
  2. كل رقم بيزوّد العداد بتاعه. O(n).
  3. <= مش <، لأن maxVal نفسه قيمة ممكنة. ده نفس off-by-one بتاع FizzBuzz: لو كتبت < هتضيّع أكبر رقم.
  4. بنكتب v عدد مرات ظهوره. الـ loopين مع بعض بيعملوا n push بالظبط، زائد k لفة على القيم: O(n + k).

لو فيه أرقام سالبة، اطرح الـ min: count[x - min]++. ولو الـ range ضخم (قيم لحد 10⁹)، الـ count array هتبقى أكبر من الـ memory، فارجع للـ comparison sort. Sort Colors (75) هي counting sort بـ k = 2، و Height Checker (1051) أطوالها من 1 لـ 100.

كده عندك الأدوات. الجزء الجاي هو أكتر حاجة الـ sort بيتسأل فيها في الانترفيو: الـ intervals. وأول سؤال: إمتى اتنين intervals يبقوا متداخلين؟

Intervals: الأساسيات

الـ interval هو [start, end]: meeting، حجز، رحلة. والمسائل كلها بتدور حوالين سؤال واحد: مين متداخل مع مين؟

تشبيه ملعب خماسي: حجز من 8 لـ 10، وحجز من 10 لـ 12. متداخلين؟ لأ، الأولانيين بيخرجوا الساعة 10 والتانيين بيدخلوا الساعة 10. بس لو بتسأل "فيه لحظة الملعب كان فيه حد؟" فالساعة 10 بالظبط تتحسب على الاتنين. نفس الأرقام، والإجابة بتفرق حسب المسألة.

القاعدة 1: رتّب بالـ start

بعد الترتيب بالـ start، أي interval جديد يا إما بيتداخل مع آخر مجموعة، يا إما بيبدأ مجموعة جديدة. ليه آخر مجموعة بس؟ لأن كل المجموعات اللي قبلها خلصت قبل ما الأخيرة تبدأ، والـ interval الجديد بيبدأ بعد بداية الأخيرة. من غير ترتيب، هتقارن كل interval بكل مجموعة: O(n²).

القاعدة 2: شرط التداخل

لو a بيبدأ قبل b (مترتبين)، هما متداخلين لو b.start <= a.end. ولو الاتنين مش مترتبين، القاعدة العامة: أكبر start أصغر من أو يساوي أصغر end.

القاعدة 3: اللمس بيتحسب ولا لأ؟

ده أكتر off-by-one بيوقّع الناس في الـ intervals. اقرا المسألة كويس، والجدول ده هتحتاجه في الأمثلة الجاية:

المسألة[1,3] و [3,5]الشرط
56 Merge، 57 Insertمتداخلين: يبقوا [1,5]start <= lastEnd
435 Non-overlappingمش متداخلينstart >= lastEnd يبقى تمام
452 Arrowsسهم واحد عند 3 بيفرقع الاتنينstart <= arrowX اتفرقع
986 Intersectionsالتقاطع [3,3]lo <= hi
1094 Car Poolingالراكب ينزل عند 3 قبل ما التاني يركبالـ drop off قبل الـ pick up

طب نطبّق القاعدة 1 والقاعدة 2 على أشهر مسألة intervals.

مثال محلول 1: Merge Intervals

Merge Intervals

mediumLeetCode 56

عندك list of intervals مش مترتبة. أي اتنين متداخلين أو بيلمسوا بعض ادمجهم في واحد، ورجّع الـ intervals اللي فضلت.

Input: [[8,10],[1,3],[2,6],[15,18],[6,7],[16,17]] Output: [[1,7],[8,10],[15,18]] Input: [[1,4],[4,5]] → [[1,5]] (touching merges) Input: [[1,10],[2,3]] → [[1,10]] (one inside the other)

نفكّر فيها مع بعض

  1. افهم: المتداخل يتدمج، واللمس هنا بيتحسب تداخل.
  2. Brute force: دوّر على أي اتنين متداخلين وادمجهم، وكرر لحد ما مفيش. كل لفة O(n²) وممكن تلف n مرة. بطيء جدًا.
  3. الـ key insight: رتّب بالـ start (القاعدة 1). بعدها كل interval يا يكبّر آخر مجموعة، يا يبدأ مجموعة جديدة. قرار واحد مع آخر عنصر بس.
  4. الـ plan: sort، وبعدين loop: لو start <= last.end كبّر الـ end، غير كده push.
  5. Edge cases: interval واحد، لمس، interval جوه interval (ودي اللي بتوقّع الناس).
  1. comparator بالـ start. sort() لوحدها هترتّب الـ intervals كنصوص، و "10,12" هتيجي قبل "8,10".
  2. لما res فاضية، res[-1] بترجع undefined من غير error (JS مفيهاش negative index). عشان كده الـ check اللي تحت.
  3. الـ last && للفة الأولى. و <= لأن اللمس بيتدمج هنا: [1,4] و [4,5] يبقوا [1,5]. مع < هيفضلوا منفصلين.
  4. ليه Math.max مش end بس؟ عشان الـ interval الجديد ممكن يبقى جوه المجموعة. [1,10] وبعده [2,3]: لو كتبت last[1] = end المجموعة هتصغر لـ [1,3].
  5. بنعمل push لـ array جديدة مش للـ input نفسه، لأن السطر 7 بيعدّل last[1]، ومش عايزين نعدّل data الـ caller.
Inputالمتوقعليه الحالة دي مهمة
[[5,6]][[5,6]]interval واحد: يتعمله push ويخلص
[[1,4],[4,5]][[1,5]]لمس: هنا بيفرق <= عن <
[[1,10],[2,3]][[1,10]]من غير Math.max هتطلع [[1,3]]
[[1,2],[3,4]][[1,2],[3,4]]فيه gap بين 2 و 3، فمش بيتدمجوا

Complexity: الـ sort O(n log n) والـ loop O(n)، يعني O(n log n). والـ memory O(n) للـ result.

في الانترفيو قول بصوت عالي: "بعد الـ sort بالـ start، كل المجموعات اللي قبل الأخيرة خلصت قبل ما الأخيرة تبدأ، فبقارن بالأخيرة بس". الجملة دي هي اللي بتثبت إن الحل صح.

طب لو الـ intervals مترتبة جاهزة وعايز تضيف واحد بس، هل لازم تعمل sort تاني؟

مثال محلول 2: Insert Interval

Insert Interval

mediumLeetCode 57

عندك intervals مترتبة بالـ start ومفيش بينها تداخل. ضيف newInterval، وادمجه مع أي حاجة بيتداخل معاها، ورجّع list مترتبة من غير تداخل.

Input: intervals = [[1,3],[4,5],[6,8],[10,12],[14,15]], newInterval = [5,10] Output: [[1,3],[4,12],[14,15]] Input: intervals = [], newInterval = [2,5] → [[2,5]] Input: intervals = [[1,5]], newInterval = [2,3] → [[1,5]]

الجديد هنا إن الـ input مترتب جاهز، فهنستغل ده ونعملها في O(n) من غير sort.

نفكّر فيها مع بعض

  1. الحل السهل: ضيف الجديد في الآخر ونادي merge بتاعة المثال 1. ده O(n log n) وصح، وقوله كبداية.
  2. الـ key insight: الـ list مترتبة ومفيش تداخل، فالـ ends كمان مترتبة. فالـ intervals بتتقسم لـ 3 مناطق ورا بعض:
  3. المنطقة 1: اللي بيخلص قبل ما الجديد يبدأ (end < s): انسخه زي ما هو.
  4. المنطقة 2: اللي بيبدأ قبل ما الجديد يخلص (start <= e): ابلعه في الجديد بـ min و max.
  5. المنطقة 3: الباقي: انسخه. Edge cases: list فاضية، الجديد قبل الكل أو بعد الكل، الجديد بيغطي الكل.
  1. let مش const لأن s و e هيكبروا. والـ destructuring بينسخ الأرقام، فمش بنعدّل newInterval نفسه.
  2. i < n الأول، وإلا intervals[n] هتبقى undefined و [1] عليها TypeError. و < strict: interval بيخلص عند s بالظبط بيلمس الجديد، فمكانه المنطقة 2 مش 1.
  3. ليه مش بنشيك على الـ end هنا؟ لأن المنطقة 1 خدت كل اللي end < s، فأي حاجة فاضلة الـ end بتاعها >= s. فالتداخل بقى محتاج start <= e بس. و <= عشان اللمس بيتدمج.
  4. أول واحد في المنطقة 2 ممكن يبدأ قبل s، وآخر واحد ممكن يخلص بعد e. الـ min والـ max بيغطّوا الحالتين.
  5. بنعمل push للجديد دايمًا، حتى لو المنطقة 2 فاضية، وفي المكان ده بالظبط بين المنطقتين عشان الترتيب يفضل صح.
Inputالمتوقعليه الحالة دي مهمة
[], [2,5][[2,5]]كل الـ loops ما بتلفش، والسطر 15 لوحده بيشتغل
[[5,6]], [1,2][[1,2],[5,6]]الجديد قبل الكل: المنطقة 1 فاضية
[[1,2],[3,4]], [0,10][[0,10]]الجديد بيبلع الكل
[[1,5]], [2,3][[1,5]]الجديد جوه واحد موجود: الـ min والـ max بيرجّعوا [1,5]

Complexity: كل interval بيتلمس مرة واحدة، O(n) time و O(n) للـ result.

في المثالين دول كنا بندمج. طب لو المطلوب العكس: تشيل أقل عدد عشان الباقي ما يتداخلش؟ هل الترتيب بالـ start لسه صح؟

مثال محلول 3: Non-overlapping Intervals

Non-overlapping Intervals

mediumLeetCode 435

إيه أقل عدد intervals تشيلهم عشان الباقي ما يبقاش فيه أي اتنين متداخلين؟ هنا اللمس مش تداخل: [1,2] و [2,3] عادي.

Input: [[1,10],[2,3],[3,5],[4,6],[6,8],[9,11]] Output: 2 (remove [1,10] and [4,6]) Input: [[1,2],[2,3]] → 0 (touching is fine) Input: [[1,2],[1,2],[1,2]] → 2

الجديد هنا إن الترتيب بالـ start بيدّي إجابة غلط، ولازم نرتّب بالـ end.

نفكّر فيها مع بعض

  1. اقلب السؤال: أقل حذف = n ناقص أكبر عدد تقدر تحتفظ بيه من غير تداخل. دي مسألة كلاسيك اسمها activity selection.
  2. Brute force: جرّب كل subset، O(2ⁿ).
  3. Greedy: نحتفظ بمين الأول؟ باللي بيخلص بدري. ليه؟ عشان بيسيب أكبر مساحة فاضية على الـ timeline للباقيين.
  4. الإثبات (exchange argument): خد أي حل optimal. أول interval فيه بيخلص عند نقطة >= أبدر end موجود. بدّله بالـ interval اللي بيخلص بدري: ولا حاجة بعده هتتعارض، لأنهم كلهم بيبدأوا بعد end الأول، وده أكبر من أو يساوي الـ end الجديد. نفس العدد، يعني لسه optimal.
  5. ليه مش الـ start؟ اللي بيبدأ بدري ممكن يبقى طويل جدًا زي [1,10]، ويقفل الطريق على الكل. الـ start مش بيقول أي حاجة عن هو هيخلص إمتى.

شوف الترتيب بالـ start وهو بيغلط على نفس الـ input:

شال 5 والإجابة الصح 2. الـ [1,10] اتاخد عشان بدأ الأول، وقفل على كل اللي بعده. دلوقتي نفس الكود بالظبط، بس بالـ end:

  1. a[1] - b[1]: بالـ end. ده السطر الوحيد اللي بيفرق عن الحل الغلط.
  2. -Infinity مش 0: الـ starts ممكن تبقى سالبة. لو بدأت بـ 0، interval زي [-5,-1] هيتشال غلط. مع -Infinity أول interval بيعدّي دايمًا.
  3. >= مش > لأن اللمس مسموح هنا. مع >، [2,3] بعد [1,2] هيتشال غلط.
  4. مش محتاجين Math.max زي الـ merge، لأن الترتيب بالـ end بيضمن إن end >= lastEnd دايمًا.
  5. اللي بيتداخل بنسيبه. وده آمن لأن اللي احتفظنا بيه بيخلص قبله أو معاه، فهو "أقل ضرر" على الباقي.
Inputالمتوقعليه الحالة دي مهمة
[[1,2],[2,3]]0اللمس: هنا بيفرق >= عن >
[[1,2],[1,2],[1,2]]2duplicates: بنحتفظ بواحد بس
[[-5,-1],[-3,0]]1أرقام سالبة: ليه -Infinity
[[3,4]]0interval واحد

Complexity: O(n log n) للـ sort، والـ loop O(n).

حل تاني صح برضه ممكن ترتّب بالـ start، بس لما يحصل تداخل تشيل اللي بيخلص متأخر: removed++; lastEnd = Math.min(lastEnd, end);. نفس الفكرة بالظبط: دايمًا خلي اللي بيخلص بدري. اختار واحد واحفظه.

طب لو اللمس بقى بيتحسب تداخل، الكود ده هيتغير فين؟

مثال محلول 4: Minimum Number of Arrows

Minimum Number of Arrows to Burst Balloons

mediumLeetCode 452

كل بالونة عبارة عن interval أفقي [xstart, xend]. السهم بيتضرب رأسي عند نقطة x، وبيفرقع أي بالونة فيها xstart <= x <= xend. أقل عدد أسهم يفرقع الكل؟

Input: [[3,9],[1,4],[7,12],[2,5],[12,15],[16,18]] Output: 3 (arrows at x = 4, 12, 18) Input: [[1,2],[2,3]] → 1 (one arrow at 2: touching counts) Input: [[1,2],[3,4]] → 2

الجديد هنا إن اللمس بيتحسب، فالشرط بيتقلب من >= لـ >. غير كده الحل هو 435 بالظبط.

نفكّر فيها مع بعض

  1. البالونة اللي بتخلص بدري لازم يتضرب فيها سهم عند نقطة <= نهايتها. أحسن مكان؟ عند نهايتها بالظبط، أبعد نقطة يمين، عشان يلحق أكبر عدد من اللي بعدها.
  2. بعد الترتيب بالـ end، أي بالونة start <= arrowX اتفرقعت، لأن الـ end بتاعها >= arrowX أكيد.
  3. أول بالونة start > arrowX محتاجة سهم جديد، عند نهايتها هي.
  4. Edge cases: القيم من -2³¹ لـ 2³¹ - 1. في C++ الـ a[1] - b[1] بيعمل overflow في int، في JS لأ. والـ -Infinity بتحمينا من البداية.
  1. بالـ end، لنفس سبب 435: البالونة اللي بتخلص بدري هي اللي بتحدد آخر مكان ينفع فيه السهم.
  2. قبل أي سهم، مفيش بالونة اتفرقعت. -Infinity بتضمن إن أول بالونة تاخد سهم.
  3. > مش >=: لو start === arrowX البالونة بتلمس السهم فاتفرقعت. قارن بـ 435: هناك >= كان معناه "مش متداخل"، هنا > معناه "السهم فاتها".
  4. السهم عند end مش start: أبعد نقطة يمين لسه بتفرقع البالونة دي، فبتلحق أكبر عدد من اللي بعدها.
Inputالمتوقعليه الحالة دي مهمة
[[1,2],[2,3]]1اللمس: مع >= هتطلع 2
[[1,2],[3,4]]2فيه gap
[[-2147483648,2147483647]]1أرقام حدود الـ int: overflow في C++ مش في JS

Complexity: O(n log n). ولو حطيت 435 و 452 جنب بعض، هتلاقيهم نفس الكود بحرف واحد مختلف. ده الـ pattern.

لحد دلوقتي كانت عندنا list واحدة. طب لو عندك اتنين lists، كل واحدة مترتبة، وعايز التقاطع بينهم؟

مثال محلول 5: Interval List Intersections

Interval List Intersections

mediumLeetCode 986

عندك list A و list B، كل واحدة مترتبة ومفيش جواها تداخل (closed intervals). رجّع كل التقاطعات بين الاتنين.

Input: A = [[0,1],[3,5],[9,12],[14,15]], B = [[2,4],[6,10],[11,14]] Output: [[3,4],[9,10],[11,12],[14,14]] Input: A = [], B = [[1,2]] → []

الجديد هنا إن مفيش sort خالص: الاتنين مترتبين، فبنمشي عليهم بـ two pointers زي الـ merge في merge sort.

نفكّر فيها مع بعض

  1. Brute force: كل interval في A مع كل interval في B: O(n·m).
  2. تقاطع اتنين: [max(starts), min(ends)]، ولو الـ max أكبر من الـ min يبقى مفيش تقاطع (القاعدة 2).
  3. نحرّك مين؟ اللي بيخلص الأول. لو A[i] خلص قبل B[j]، فكل اللي بعد B[j] بيبدأ بعد ما B[j] يخلص، يعني بعد A[i] ما يخلص بكتير. فـ A[i] مالوش أي تقاطع تاني، نشيله.
  4. Edge cases: list فاضية، تقاطع في نقطة واحدة زي [14,14]، اتنين بيخلصوا في نفس النقطة.
  1. &&: أول ما list تخلص، مفيش تقاطعات تانية، حتى لو التانية لسه فيها.
  2. التقاطع بيبدأ عند آخر start وبيخلص عند أول end. ده الشرط العام من القاعدة 2.
  3. <= مش <: الـ intervals closed، فـ lo === hi تقاطع في نقطة واحدة وبيتحسب.
  4. بنحرّك اللي بيخلص الأول. لو الاتنين بيخلصوا في نفس النقطة، الـ else بيحرّك j، واللفة الجاية A[i] مع B[j + 1] مش هيتقاطعوا فـ i يتحرك. صح برضه.

Complexity: كل لفة بتحرّك pointer واحد، فـ O(n + m) time. ده بالظبط merge بتاع merge sort، بس بدل ما ناخد الأصغر بناخد التقاطع.

آخر نوع: مش "مين متداخل مع مين"، لكن "كام واحد متداخلين في نفس اللحظة؟". ده مش هيتحل بمقارنة مع آخر interval.

مثال محلول 6: Sweep line و Car Pooling

سؤال زي "محتاج كام قاعة اجتماعات؟" معناه: إيه أكبر عدد meetings شغالة في نفس اللحظة. الـ key insight: حوّل كل interval لـ 2 events: +1 عند البداية و -1 عند النهاية. رتّب الـ events بالوقت، وامشي عليهم بعدّاد. ده الـ prefix sum اللي في Prefix Sum بالظبط، بس على timeline.

تشبيه عدّاد ركاب الميكروباص: في كل محطة ناس بتنزل وناس بتركب. السواق مش محتاج يفتكر مين راكب، محتاج العدد بس. والمهم: في نفس المحطة، اللي نازل ينزل الأول وبعدين اللي طالع يطلع.

Car Pooling

mediumLeetCode 1094

عربية فيها capacity كرسي، وماشية في اتجاه واحد. كل رحلة [num, from, to]: num راكب بيركبوا عند from وبينزلوا عند to. هل تقدر توصّل الكل من غير ما العربية تزيد عن الـ capacity في أي لحظة؟

Input: trips = [[2,1,5],[3,5,8],[1,3,6]], capacity = 4 → true Input: trips = [[2,1,5],[3,5,8],[1,3,6]], capacity = 3 → false

الجديد هنا إن بنرتّب events مش intervals، والـ tie-break في الـ comparator (اللي في نفس المكان مين الأول) هو اللي بيحدد الإجابة.

نفكّر فيها مع بعض

  1. Brute force: لكل نقطة على الطريق اجمع ركاب كل الرحلات اللي شغالة. O(range × n).
  2. Events: كل رحلة بتدّي [from, +num] و [to, -num]. رتّبهم بالمكان، وامشي بـ load.
  3. الـ tie-break: في نفس المكان، النزول (السالب) قبل الركوب. عند 5 في المثال: 2 بينزلوا و 3 بيركبوا. لو الركوب الأول، الـ load هيوصل 6 للحظة، وده غلط لأنهم ما كانوش في العربية مع بعض.
  4. Edge cases: العربية مليانة بالظبط (load === capacity مسموح)، رحلات بتبدأ في نفس النقطة.
  1. الـ destructuring بنفس ترتيب المسألة: [num, from, to]. لو بدّلتهم، كل حاجة هتبوظ من غير error.
  2. كل رحلة = 2 events. عند to الركاب بينزلوا، فمش محسوبين في العربية عند to.
  3. الـ multi-key comparator: بالمكان، ولو نفس المكان a[1] - b[1] بيحط السالب الأول، يعني النزول قبل الركوب.
  4. [, delta]: الفاصلة الأولانية معناها "سيب أول عنصر"، محتاجين الـ delta بس.
  5. > مش >=: العربية مليانة بالظبط مسموح.

Complexity: 2n event، والـ sort O(n log n). وبما إن الأماكن في المسألة دي لحد 1000 بس، فيه حل O(n + 1000) بالـ difference array من Prefix Sum: diff[from] += num; diff[to] -= num; وبعدين prefix sum.

نفس الكود لـ "كام قاعة محتاج؟"

المسألة دي (Meeting Rooms II) premium على LeetCode، بس 2406 نسخة مجانية منها، مع فرق واحد: الـ intervals هناك closed، فاللمس تداخل، والـ +1 لازم ييجي قبل الـ -1 في نفس اللحظة (أو حط الـ -1 عند e + 1).

كده خلصنا الأنواع الأربعة. قبل ما تتمرن، خلينا نجمع الغلطات اللي بتتكرر في كل ده.

غلطات مشهورة

1. sort() من غير comparator

الصح: (a, b) => a - b للأرقام، و (a, b) => a[0] - b[0] للـ intervals. مفيش حالة في الانترفيو الـ default sort فيها صح غير strings lowercase.

2. comparator بيرجّع boolean

الـ comparator لازم يرجّع رقم سالب لما a قبل b. الـ boolean عمره ما بيبقى سالب، فالـ engine مش بيعرف يقدّم أي عنصر.

3. نسيت Math.max في الـ merge

الصح: last[1] = Math.max(last[1], end). الـ interval الجديد ممكن يخلص قبل المجموعة.

4. ترتيب بالـ start في 435 و 452

لما المطلوب "أكبر عدد مش متداخل"، رتّب بالـ end. اللي بيخلص بدري بيسيب مكان أكتر.

5. قاعدة اللمس غلط

ارجع لجدول "اللمس بيتحسب ولا لأ" واقرا المسألة: في 56 و 452 اللمس تداخل (<=)، في 435 و 1094 لأ.

6. الـ sort غيّر الـ input

لو محتاج الترتيب الأصلي بعدين، رتّب نسخة: [...nums].sort(...) أو nums.toSorted(...).

اختبر نفسك

[5, 25, 100, 1].sort() بترجع إيه؟

  • [1, 5, 25, 100]
  • [1, 100, 25, 5]
  • [100, 25, 5, 1]
  • error

من غير comparator بتتقارن كـ strings: "1" < "100" < "25" < "5"، لأن المقارنة حرف حرف، و '1' < '2' < '5'.

عايز ترتّب لاعيبة بالـ score تنازلي، ولو متساويين بالاسم تصاعدي. أنهي comparator؟

  • (p, q) => p.score - q.score || p.name.localeCompare(q.name)
  • (p, q) => q.score - p.score || p.name.localeCompare(q.name)
  • (p, q) => q.score - p.score && p.name.localeCompare(q.name)
  • (p, q) => q.score > p.score

q - p بيعكس الترتيب فيبقى تنازلي. والـ || بيروح للاسم بس لما فرق الـ score يبقى 0. الـ && هيرجّع 0 لما الـ scores متساوية من غير ما يبص على الاسم.

[1,3] و [3,5]: في Merge Intervals (56) وفي Non-overlapping Intervals (435)، الإجابة إيه؟

  • في الاتنين متداخلين
  • في الاتنين مش متداخلين
  • في 56 يتدمجوا لـ [1,5]، وفي 435 مش متداخلين فمش محتاج تشيل حاجة
  • في 56 مش متداخلين، وفي 435 متداخلين

كل مسألة بتحدد قاعدة اللمس. عشان كده 56 فيها start <= lastEnd، و 435 فيها start >= lastEnd للاحتفاظ.

في Non-overlapping Intervals، ليه بنرتّب بالـ end مش بالـ start؟

  • عشان الـ sort بالـ end أسرع
  • عشان اللي بيخلص بدري بيسيب أكبر مساحة للباقي، واللي بيبدأ بدري ممكن يبقى طويل ويقفل على الكل
  • الاتنين صح، مش فارقة
  • عشان الـ end دايمًا أكبر من الـ start

على [[1,10],[2,3],[3,5],[4,6],[6,8],[9,11]] الترتيب بالـ start (مع الاحتفاظ بأول واحد) بيشيل 5، والـ end بيشيل 2 بس.

عندك 10⁵ رقم، كل رقم بين 0 و 10⁹. counting sort مناسب؟

  • آه، هو O(n) دايمًا
  • لأ، الـ k = 10⁹ فالـ count array هتبقى مليار خانة. استخدم comparison sort
  • آه لو الأرقام موجبة
  • لأ، عشان counting sort مش stable

counting sort هو O(n + k) time و O(k) memory. بيكسب بس لما k صغير، زي درجات من 0 لـ 100.

ليه merge sort لازم يكون O(n log n) حتى لو الـ input مترتب أصلًا، بينما quicksort بالـ last pivot بيبقى O(n²) على نفس الـ input؟

  • merge sort دايمًا بيقسم في النص بالظبط، أما quicksort فالقسمة بتعتمد على الـ pivot، ومع array مترتبة الـ pivot بيبقى أكبر واحد
  • عشان merge sort بيستخدم memory أكتر
  • عشان quicksort مش stable
  • الكلام ده غلط، الاتنين O(n log n) دايمًا

عمق الـ recursion في merge sort دايمًا log n. في quicksort العمق بيعتمد على الـ pivot: لو كل مرة بيشيل عنصر واحد، العمق n والشغل n²/2.

تمرين: فكّر قبل ما تفتح

Remove Covered Intervals

mediumLeetCode 1288

الـ interval [a,b] يبقى "متغطي" لو فيه interval تاني [c,d] يغطّيه، يعني c <= a و b <= d. شيل كل المتغطي ورجّع عدد اللي فضل.

[[1,4],[3,6],[2,8]] → 2 ([3,6] is inside [2,8]) [[1,4],[1,6],[2,5],[7,9]] → 2
تلميح 1

رتّب بالـ start. كده أي interval ممكن يتغطى بس من حاجة جت قبله. احتفظ بأكبر end شفته: لو الـ end الحالي <= منه، يبقى متغطي.

تلميح 2

طب [1,4] و [1,6]؟ ليهم نفس الـ start، ولو [1,4] جه الأول هيتحسب غلط. في نفس الـ start حط الأطول الأول: الـ end تنازلي. ده السطر 6 في الـ comparators.

الحل

الـ > strict لأن end === maxEnd مع start أكبر أو مساوي معناه إنه متغطي. ومش محتاجين نشيك على الـ start، الترتيب ضمنه. O(n log n).

اتمرن على LeetCode بالترتيب

كل مسألة بتضيف فكرة واحدة على اللي قبلها. أول 5 للـ sorting نفسه، والباقي intervals بنفس ترتيب الفصل.

الخلاصة

في جملة واحدة رتّب الأول، والمسألة تبقى قرار واحد مع آخر عنصر: بالـ start لما تدمج، بالـ end لما تختار أكبر عدد مش متداخل، وبالـ events لما تعدّ كام واحد في نفس اللحظة. وقبل أي شرط اسأل: اللمس بيتحسب ولا لأ؟
السؤالالإجابة
أرتّب بالـ start ولا بالـ end؟start لما تدمج أو تضيف. end لما تختار أكبر عدد مش متداخل أو أقل أسهم.
<= ولا <؟حسب اللمس: لو [1,3] و [3,5] متداخلين يبقى <=. اقرا المسألة.
ليه Math.max في الـ merge؟عشان interval ممكن يبقى جوه المجموعة.
أبدأ lastEnd بكام؟-Infinity، عشان الأرقام ممكن تبقى سالبة.
الـ JS sort stable؟آه من ES2019. std::sort في C++ لأ.
Complexity؟أي sort بالمقارنة O(n log n). counting sort O(n + k) لو الـ range صغير. 57 و 986 O(n) لأنهم مترتبين جاهز.

الفصل الجاي: الـ array المترتبة مش بس بتسهّل الـ intervals. هي بتفتحلك أسرع طريقة بحث ممكنة: Binary Search، اللي بتشيل نص الاحتمالات في كل خطوة، فبتلاقي أي رقم في مليون عنصر في 20 خطوة بس. وهتشوف هناك إنها مش للـ arrays بس: تقدر تعمل binary search على الإجابة نفسها.