Sorting و Intervalsmerge sort · quicksort · comparators · counting sort · intervals · sweep line
الـ sort هو أشهر preprocessing step في الانترفيو: ترتّب الأول، والمسألة اللي كانت O(n²) تبقى loop واحدة. هتفهم الـ sort شغال إزاي من جوه، وتكتب أي comparator في JS صح، وبعدين تستخدمه في عيلة كاملة من المسائل: الـ intervals.
هتطلع من الفصل ده وإنت عارف
- تكتب 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 وإنت عمرك ما هتكتبه في الانترفيو؟ عشان:
- أي حل فيه sort يبقى O(n log n) على الأقل، ولازم تعرف ليه.
- فكرة الـ merge (تدمج اتنين مترتبين) بتتكرر: Merge Sorted Array، Merge Two Lists، و Interval Intersections اللي هنحلها هنا.
- ساعات الـ interviewer بيقول "من غير built-in sort"، أو يسأل "الـ sort بتاع JS stable؟".
الطريقة البديهية اللي أي حد بيرتّب بيها: دوّر على أصغر رقم وحطه في الأول، وبعدين أصغر رقم في الباقي، وهكذا. اسمها selection sort:
عدّ معاه المقارنات على 6 أرقام بس:
15 مقارنة على 6 أرقام، يعني n(n - 1) / 2، يعني O(n²). على n = 100,000 ده 5 مليار مقارنة، يعني TLE. الـ merge sort هيعملها في حوالي 1.7 مليون.
بس قبل ما نشوف إزاي الـ sort بيشتغل، إمتى أصلًا تفكّر إنك ترتّب؟
إمتى ترتّب؟ وإزاي تعرف مسألة intervals
الـ sort بيبوّظ الترتيب الأصلي، فلو المطلوب indices أو subarray متصلة، الترتيب بيضيّع المعلومة اللي محتاجها. ولو الـ array مترتبة أصلًا، يبقى المطلوب غالبًا binary search أو two pointers.
في الـ intervals بالذات، فيه 4 أنواع، وكل نوع ليه ترتيب وشرط:
| النوع | ترتّب بإيه | القرار | مسائل |
|---|---|---|---|
| ادمج المتداخل | start | start <= lastEnd يبقى ادمج | 56، 57 |
| أكبر عدد مش متداخل / أقل حذف | end | start >= 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 خطوات:
- لو الـ array فيها عنصر واحد أو فاضية، هي مترتبة أصلًا. ده الـ base case.
- غير كده، قسّمها نصين، ورتّب كل نص بنفس الدالة.
- ادمج النصين المترتبين في array واحدة مترتبة.
الدالة بتنادي نفسها، وده اسمه recursion، وليه فصل كامل (Recursion). هنا كفاية تثق إن "رتّب النص" بيرجّعلك نص مترتب. الشغل الحقيقي كله في الـ merge.
- ليه
<= 1مش=== 1؟ عشان الـ input نفسه ممكن يبقى فاضي. ومن غير base case خالص، array فيها عنصر واحد هتتقسم لـ[]ونفس العنصر، فهتنادي نفسك على نفس الحجم للأبد:Maximum call stack size exceeded. - الـ
Math.floorلأن القسمة في JS مش بتقطع زي C++:5 / 2 = 2.5، ومفيش index اسمه 2.5. مع 5 عناصر، الشمال 2 واليمين 3. - الـ
slice(0, mid)بياخد من 0 لحدmid - 1، لأن الـ end فيsliceexclusive. - الـ
slice(mid)منmidللآخر. الاتنين مع بعض بيغطّوا كل عنصر مرة واحدة بالظبط. لو كتبتslice(mid + 1)هتضيّعarr[mid]. - هنا النصين مترتبين، فاضل ندمجهم.
iوjبيشاوروا على أول عنصر لسه ما اتاخدش في كل نص. ده نفس الـ two pointers، بس كل pointer في array لوحده.&&مش||: بنقارن بس طول ما الاتنين فيهم عناصر. مع||، لوbخلص هتقارنa[i] <= undefined، وده false، فهتعمل push لـundefinedللأبد. infinite loop.- الـ key line. خد الأصغر. وليه
<=مش<؟ لو متساويين بناخد منaالأول، وaهو النص الشمال، يعني العناصر اللي كانت قبل في الأصل. كده المتساويين بيفضلوا بترتيبهم الأصلي، وده اسمه stable. مع<الترتيب هيطلع صح برضه، بس مش stable. - لما واحد يخلص، الباقي في التاني مترتب وكله أكبر من أي حاجة في
out، فبنلزقه زي ما هو. واحدة بس من الـ loops دي هي اللي هتلف فعلًا، بس إحنا مش عارفين أنهي واحد خلص، فبنكتب الاتنين. - بنرجّع 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 هو المكان اللي هيتحط فيه الصغير الجاي.
- الـ pivot هو آخر عنصر. سهل، بس هنشوف تحت إنه خطر على array مترتبة.
- الـ small zone هي
[lo .. i - 1]، وفي الأول فاضية، فـi = lo. ده بالظبطwriteفي قالب two pointers. j < hiمش<= hi، لأنnums[hi]هو الـ pivot نفسه، ومكانه بيتحدد في الآخر.- لقينا رقم أصغر، فبنعمل swap مع أول خانة بعد الـ small zone وبنكبّرها. swap مش copy، عشان اللي كان عند
iرقم كبير، وما ينفعش يضيع. - كل اللي قبل
iأصغر من الـ pivot، وكل اللي منiلـhi - 1أكبر أو يساوي. فمكان الـ pivot الصح هوiبالظبط. >=مش===: لو الـ pivot وقف عندlo، النداءquickSort(lo, p - 1)بيبقى range فاضي فيهlo > hi.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 sort | Quicksort | JS sort (V8: TimSort) | Counting sort | |
|---|---|---|---|---|
| Time | O(n log n) دايمًا | O(n log n) average، O(n²) worst | O(n log n)، و O(n) لو شبه مترتبة | O(n + k) |
| Memory | O(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₂ n | n² |
|---|---|---|---|
| 3 | 2.6 → 3 | 4.8 | 9 |
| 8 | 15.3 → 16 | 24 | 64 |
| 1,000 | ~8,530 | ~9,966 | 1,000,000 |
| 100,000 | ~1.52M | ~1.66M | 10,000M |
يعني الـ sort أصلًا أبطأ من O(n). طب لما بتستخدم الـ built-in، فيه حاجة تانية لازم تعرفها: لو عنصرين متساويين، مين يطلع الأول؟
Stability: ترتيب المتساويين
الـ sort يبقى stable لو العناصر المتساوية (حسب الـ comparator) فضلت بنفس ترتيبها الأصلي. مع أرقام لوحدها مش فارقة، 5 زي 5. بس مع objects فارقة جدًا:
- JS:
Array.prototype.sortمضمون stable من ES2019 (Node 12 وأي browser حديث). - C++:
std::sortمش stable. لو محتاجه استخدمstd::stable_sort. خلي بالك من دي في حلولك على LeetCode. - Python:
sortedوlist.sortstable.
الـ stability جاية منين في الكود؟ في الـ merge من <=، وهتشوفها في الجزء الجاي في insertion sort من > 0. والجزء الجاي هو الأهم عمليًا: إزاي تقول للـ sort "رتّب بالطريقة دي".
الـ comparator في JS بالتفصيل
الفخ الأول: sort() من غير comparator بيحوّل كل حاجة لـ string ويقارن حرف حرف:
العقد بتاع الـ comparator: cmp(a, b) بيرجّع رقم:
- سالب:
aقبلb. - موجب:
aبعدb. - صفر: متساويين، سيبهم بترتيبهم (stable).
كل الأشكال اللي هتحتاجها في الانترفيو في مكان واحد:
- لو
a = 2وb = 10،a - b = -8سالب، فالـ 2 قبل الـ 10. ده ascending. وفي JS الأرقام doubles، فـa - bمش بيعمل overflow حتى مع أرقام قريبة من2³¹، عكسintفي C++. - عكس الطرح يعكس الترتيب. بلاش
sort(a - b).reverse(): شغل زيادة، وبيعكس ترتيب المتساويين فبيبوّظ الـ stability. - بالـ start بس. الـ intervals اللي ليها نفس الـ start بتفضل بترتيبها الأصلي.
- الـ multi-key trick: لو
a[0] - b[0]طلع0، والـ0falsy، فالـ||بيروح للـ key التاني. لو مش صفر، هو الإجابة على طول. - الـ key التاني معكوس: start تصاعدي، ولو الـ start واحد، الأطول الأول. هتحتاجه في التمرين آخر الفصل.
- آمن بس مع كلمات lowercase. الحروف الكبيرة كلها قبل الصغيرة (
'Z'كوده 90 و'a'كوده 97)، فـ['b', 'A', 'a', 'B']بتطلع['A', 'B', 'a', 'b']. - الـ
localeCompareبيرتّب زي القاموس:['a', 'A', 'b', 'B']، وبيرجّع رقم سالب أو صفر أو موجب. أبطأ شوية، استخدمه لما الكلام عن أسامي ناس. - نفس ترتيب الـ default، بس كـ رقم، فتقدر تحطه جوه comparator بأكتر من key.
- بالطول الأول، ولو الطول واحد بالترتيب الأبجدي.
- objects: الـ score تنازلي، ولو متساوي الاسم تصاعدي.
- 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؟".
- الـ invariant:
arr[0 .. i - 1]مترتب. عنصر واحد مترتب لوحده، فنبدأ منi = 1. - بنحفظ
xفي متغير لأن الـ shift هيكتب فوقarr[i]. j >= 0الأول عشان الـ short-circuit يحمينا منarr[-1]. و> 0مش>= 0: لو الـ comparator قال صفر (متساويين) نقف، فـxيفضل بعد المساوي ليه. ده اللي بيخلّيه stable.- نزق العنصر الأكبر خطوة يمين عشان نفضّي مكان.
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 بيستخدمه على الأجزاء الصغيرة.
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.
maxVal + 1لأن القيم من 0 لـmaxVal، يعنيmaxVal + 1قيمة. والـfill(0)ضروري:new Array(n)لوحدها خانات فاضية، وundefined + 1بيطلعNaN.- كل رقم بيزوّد العداد بتاعه. O(n).
<=مش<، لأنmaxValنفسه قيمة ممكنة. ده نفس off-by-one بتاع FizzBuzz: لو كتبت<هتضيّع أكبر رقم.- بنكتب
vعدد مرات ظهوره. الـ loopين مع بعض بيعملواnpush بالظبط، زائد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، حجز، رحلة. والمسائل كلها بتدور حوالين سؤال واحد: مين متداخل مع مين؟
القاعدة 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
عندك list of intervals مش مترتبة. أي اتنين متداخلين أو بيلمسوا بعض ادمجهم في واحد، ورجّع الـ intervals اللي فضلت.
نفكّر فيها مع بعض
- افهم: المتداخل يتدمج، واللمس هنا بيتحسب تداخل.
- Brute force: دوّر على أي اتنين متداخلين وادمجهم، وكرر لحد ما مفيش. كل لفة O(n²) وممكن تلف n مرة. بطيء جدًا.
- الـ key insight: رتّب بالـ start (القاعدة 1). بعدها كل interval يا يكبّر آخر مجموعة، يا يبدأ مجموعة جديدة. قرار واحد مع آخر عنصر بس.
- الـ plan: sort، وبعدين loop: لو
start <= last.endكبّر الـ end، غير كده push. - Edge cases: interval واحد، لمس، interval جوه interval (ودي اللي بتوقّع الناس).
- comparator بالـ start.
sort()لوحدها هترتّب الـ intervals كنصوص، و"10,12"هتيجي قبل"8,10". - لما
resفاضية،res[-1]بترجعundefinedمن غير error (JS مفيهاش negative index). عشان كده الـ check اللي تحت. - الـ
last &&للفة الأولى. و<=لأن اللمس بيتدمج هنا:[1,4]و[4,5]يبقوا[1,5]. مع<هيفضلوا منفصلين. - ليه
Math.maxمشendبس؟ عشان الـ interval الجديد ممكن يبقى جوه المجموعة.[1,10]وبعده[2,3]: لو كتبتlast[1] = endالمجموعة هتصغر لـ[1,3]. - بنعمل 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.
طب لو الـ intervals مترتبة جاهزة وعايز تضيف واحد بس، هل لازم تعمل sort تاني؟
مثال محلول 2: Insert Interval
عندك intervals مترتبة بالـ start ومفيش بينها تداخل. ضيف newInterval، وادمجه مع أي حاجة بيتداخل معاها، ورجّع list مترتبة من غير تداخل.
الجديد هنا إن الـ input مترتب جاهز، فهنستغل ده ونعملها في O(n) من غير sort.
نفكّر فيها مع بعض
- الحل السهل: ضيف الجديد في الآخر ونادي
mergeبتاعة المثال 1. ده O(n log n) وصح، وقوله كبداية. - الـ key insight: الـ list مترتبة ومفيش تداخل، فالـ ends كمان مترتبة. فالـ intervals بتتقسم لـ 3 مناطق ورا بعض:
- المنطقة 1: اللي بيخلص قبل ما الجديد يبدأ (
end < s): انسخه زي ما هو. - المنطقة 2: اللي بيبدأ قبل ما الجديد يخلص (
start <= e): ابلعه في الجديد بـ min و max. - المنطقة 3: الباقي: انسخه. Edge cases: list فاضية، الجديد قبل الكل أو بعد الكل، الجديد بيغطي الكل.
letمشconstلأنsوeهيكبروا. والـ destructuring بينسخ الأرقام، فمش بنعدّلnewIntervalنفسه.i < nالأول، وإلاintervals[n]هتبقىundefinedو[1]عليها TypeError. و<strict: interval بيخلص عندsبالظبط بيلمس الجديد، فمكانه المنطقة 2 مش 1.- ليه مش بنشيك على الـ end هنا؟ لأن المنطقة 1 خدت كل اللي
end < s، فأي حاجة فاضلة الـ end بتاعها>= s. فالتداخل بقى محتاجstart <= eبس. و<=عشان اللمس بيتدمج. - أول واحد في المنطقة 2 ممكن يبدأ قبل
s، وآخر واحد ممكن يخلص بعدe. الـ min والـ max بيغطّوا الحالتين. - بنعمل 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
إيه أقل عدد intervals تشيلهم عشان الباقي ما يبقاش فيه أي اتنين متداخلين؟ هنا اللمس مش تداخل: [1,2] و [2,3] عادي.
الجديد هنا إن الترتيب بالـ start بيدّي إجابة غلط، ولازم نرتّب بالـ end.
نفكّر فيها مع بعض
- اقلب السؤال: أقل حذف =
nناقص أكبر عدد تقدر تحتفظ بيه من غير تداخل. دي مسألة كلاسيك اسمها activity selection. - Brute force: جرّب كل subset،
O(2ⁿ). - Greedy: نحتفظ بمين الأول؟ باللي بيخلص بدري. ليه؟ عشان بيسيب أكبر مساحة فاضية على الـ timeline للباقيين.
- الإثبات (exchange argument): خد أي حل optimal. أول interval فيه بيخلص عند نقطة
>=أبدر end موجود. بدّله بالـ interval اللي بيخلص بدري: ولا حاجة بعده هتتعارض، لأنهم كلهم بيبدأوا بعد end الأول، وده أكبر من أو يساوي الـ end الجديد. نفس العدد، يعني لسه optimal. - ليه مش الـ start؟ اللي بيبدأ بدري ممكن يبقى طويل جدًا زي
[1,10]، ويقفل الطريق على الكل. الـ start مش بيقول أي حاجة عن هو هيخلص إمتى.
شوف الترتيب بالـ start وهو بيغلط على نفس الـ input:
شال 5 والإجابة الصح 2. الـ [1,10] اتاخد عشان بدأ الأول، وقفل على كل اللي بعده. دلوقتي نفس الكود بالظبط، بس بالـ end:
a[1] - b[1]: بالـ end. ده السطر الوحيد اللي بيفرق عن الحل الغلط.-Infinityمش0: الـ starts ممكن تبقى سالبة. لو بدأت بـ0، interval زي[-5,-1]هيتشال غلط. مع-Infinityأول interval بيعدّي دايمًا.>=مش>لأن اللمس مسموح هنا. مع>،[2,3]بعد[1,2]هيتشال غلط.- مش محتاجين
Math.maxزي الـ merge، لأن الترتيب بالـ end بيضمن إنend >= lastEndدايمًا. - اللي بيتداخل بنسيبه. وده آمن لأن اللي احتفظنا بيه بيخلص قبله أو معاه، فهو "أقل ضرر" على الباقي.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [[1,2],[2,3]] | 0 | اللمس: هنا بيفرق >= عن > |
| [[1,2],[1,2],[1,2]] | 2 | duplicates: بنحتفظ بواحد بس |
| [[-5,-1],[-3,0]] | 1 | أرقام سالبة: ليه -Infinity |
| [[3,4]] | 0 | interval واحد |
Complexity: O(n log n) للـ sort، والـ loop O(n).
removed++; lastEnd = Math.min(lastEnd, end);. نفس الفكرة بالظبط: دايمًا خلي اللي بيخلص بدري. اختار واحد واحفظه.
طب لو اللمس بقى بيتحسب تداخل، الكود ده هيتغير فين؟
مثال محلول 4: Minimum Number of Arrows
كل بالونة عبارة عن interval أفقي [xstart, xend]. السهم بيتضرب رأسي عند نقطة x، وبيفرقع أي بالونة فيها xstart <= x <= xend. أقل عدد أسهم يفرقع الكل؟
الجديد هنا إن اللمس بيتحسب، فالشرط بيتقلب من >= لـ >. غير كده الحل هو 435 بالظبط.
نفكّر فيها مع بعض
- البالونة اللي بتخلص بدري لازم يتضرب فيها سهم عند نقطة
<=نهايتها. أحسن مكان؟ عند نهايتها بالظبط، أبعد نقطة يمين، عشان يلحق أكبر عدد من اللي بعدها. - بعد الترتيب بالـ end، أي بالونة
start <= arrowXاتفرقعت، لأن الـ end بتاعها>= arrowXأكيد. - أول بالونة
start > arrowXمحتاجة سهم جديد، عند نهايتها هي. - Edge cases: القيم من
-2³¹لـ2³¹ - 1. في C++ الـa[1] - b[1]بيعمل overflow فيint، في JS لأ. والـ-Infinityبتحمينا من البداية.
- بالـ end، لنفس سبب 435: البالونة اللي بتخلص بدري هي اللي بتحدد آخر مكان ينفع فيه السهم.
- قبل أي سهم، مفيش بالونة اتفرقعت.
-Infinityبتضمن إن أول بالونة تاخد سهم. >مش>=: لوstart === arrowXالبالونة بتلمس السهم فاتفرقعت. قارن بـ 435: هناك>=كان معناه "مش متداخل"، هنا>معناه "السهم فاتها".- السهم عند
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
عندك list A و list B، كل واحدة مترتبة ومفيش جواها تداخل (closed intervals). رجّع كل التقاطعات بين الاتنين.
الجديد هنا إن مفيش sort خالص: الاتنين مترتبين، فبنمشي عليهم بـ two pointers زي الـ merge في merge sort.
نفكّر فيها مع بعض
- Brute force: كل interval في A مع كل interval في B:
O(n·m). - تقاطع اتنين:
[max(starts), min(ends)]، ولو الـ max أكبر من الـ min يبقى مفيش تقاطع (القاعدة 2). - نحرّك مين؟ اللي بيخلص الأول. لو
A[i]خلص قبلB[j]، فكل اللي بعدB[j]بيبدأ بعد ماB[j]يخلص، يعني بعدA[i]ما يخلص بكتير. فـA[i]مالوش أي تقاطع تاني، نشيله. - Edge cases: list فاضية، تقاطع في نقطة واحدة زي
[14,14]، اتنين بيخلصوا في نفس النقطة.
&&: أول ما list تخلص، مفيش تقاطعات تانية، حتى لو التانية لسه فيها.- التقاطع بيبدأ عند آخر start وبيخلص عند أول end. ده الشرط العام من القاعدة 2.
<=مش<: الـ intervals closed، فـlo === hiتقاطع في نقطة واحدة وبيتحسب.- بنحرّك اللي بيخلص الأول. لو الاتنين بيخلصوا في نفس النقطة، الـ
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.
عربية فيها capacity كرسي، وماشية في اتجاه واحد. كل رحلة [num, from, to]: num راكب بيركبوا عند from وبينزلوا عند to. هل تقدر توصّل الكل من غير ما العربية تزيد عن الـ capacity في أي لحظة؟
الجديد هنا إن بنرتّب events مش intervals، والـ tie-break في الـ comparator (اللي في نفس المكان مين الأول) هو اللي بيحدد الإجابة.
نفكّر فيها مع بعض
- Brute force: لكل نقطة على الطريق اجمع ركاب كل الرحلات اللي شغالة.
O(range × n). - Events: كل رحلة بتدّي
[from, +num]و[to, -num]. رتّبهم بالمكان، وامشي بـload. - الـ tie-break: في نفس المكان، النزول (السالب) قبل الركوب. عند 5 في المثال: 2 بينزلوا و 3 بيركبوا. لو الركوب الأول، الـ load هيوصل 6 للحظة، وده غلط لأنهم ما كانوش في العربية مع بعض.
- Edge cases: العربية مليانة بالظبط (
load === capacityمسموح)، رحلات بتبدأ في نفس النقطة.
- الـ destructuring بنفس ترتيب المسألة:
[num, from, to]. لو بدّلتهم، كل حاجة هتبوظ من غير error. - كل رحلة = 2 events. عند
toالركاب بينزلوا، فمش محسوبين في العربية عندto. - الـ multi-key comparator: بالمكان، ولو نفس المكان
a[1] - b[1]بيحط السالب الأول، يعني النزول قبل الركوب. [, delta]: الفاصلة الأولانية معناها "سيب أول عنصر"، محتاجين الـ delta بس.>مش>=: العربية مليانة بالظبط مسموح.
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.
تمرين: فكّر قبل ما تفتح
الـ interval [a,b] يبقى "متغطي" لو فيه interval تاني [c,d] يغطّيه، يعني c <= a و b <= d. شيل كل المتغطي ورجّع عدد اللي فضل.
تلميح 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 بنفس ترتيب الفصل.
- Sort an Arrayاكتب merge sort من دماغك. لو جرّبت quicksort بالـ last pivot ممكن ياخد TLE، فاستخدم pivot عشوائي.
- Height Checkercounting sort: الأطوال من 1 لـ 100.
- Relative Sort Arraycounting sort بترتيب custom بدل الترتيب العادي.
- Sort Array by Increasing Frequencymulti-key comparator: الـ frequency تصاعدي، والقيمة تنازلي.
- Largest Numbercomparator غريب: قارن
b + aبـa + bكـ strings. وخلي بالك من"00". - Merge Intervalsالمثال المحلول 1. اكتبه من غير ما تبص.
- Insert Intervalالمناطق التلاتة من غير sort.
- Remove Covered Intervalsالتمرين: ترتيب بـ key تاني معكوس.
- Non-overlapping Intervalsأول مرة ترتّب بالـ end. قول الإثبات لنفسك.
- Minimum Number of Arrows to Burst Balloonsنفس 435 بقاعدة لمس مختلفة:
>بدل>=. - Interval List Intersectionstwo pointers على listين مترتبين.
- Car Poolingsweep line بالـ events، وجرّب كمان حل الـ difference array.
- Divide Intervals Into Minimum Number of GroupsMeeting Rooms II المجانية. هنا اللمس تداخل، فالـ tie-break بيتقلب.
الخلاصة
| السؤال | الإجابة |
|---|---|
| أرتّب بالـ 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 على الإجابة نفسها.