Greedylocally best choice · exchange argument · counterexamples · sort then pick · farthest reach

الـ greedy معناه: في كل خطوة خد أحسن اختيار دلوقتي، ومترجعش فيه أبدًا. لما ينفع، بيدّيك حل O(n) أو O(n log n) في كام سطر. ولما ما ينفعش، بيدّيك إجابة غلط بثقة تامة. الفصل ده عن الفرق بين الحالتين.

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

  • يعني إيه greedy بالظبط، وفرقه عن الـ DP والـ backtracking.
  • تقنع نفسك إن الـ greedy صح بالـ exchange argument بكلام بسيط، وتكسره بـ counterexample صغير لو غلط.
  • الـ patterns الأساسية: sort then pick، collect every gain، farthest reach، reset لما الحساب يبقى سالب.
  • تحل Assign Cookies و Stock II و Jump Game I و II و Gas Station و Partition Labels و Non-overlapping Intervals، كل واحدة بتضيف فكرة واحدة.

يعني إيه Greedy؟

في الفصل اللي فات كنا بنجرّب كل الاختيارات ونفتكر نتيجة كل واحد (DP). دلوقتي السؤال العكسي: إمتى تقدر تاخد أحسن اختيار قدامك وتمشي، من غير ما تبص على الباقي ولا ترجع؟

الطريقةبتعمل إيهبترجع في قرارها؟السرعة
Backtrackingتجرّب كل الطرقأيوه، بتعمل undoexponential
DPتجرّب كل الطرق بس تفتكر النتايجمش بترجع، بتقارن كل الاختياراتpolynomial، غالبًا O(n²) أو O(n × m)
Greedyتاخد الأحسن دلوقتي وبسأبدًاغالبًا O(n) أو O(n log n) بعد sort

الـ greedy أسرع حاجة فيهم، بس فيه شرط: لازم يكون أحسن اختيار دلوقتي جزء من أحسن حل في الآخر. لو الشرط ده مش متحقق، الـ greedy بيطلّع إجابة غلط من غير ما يحس.

تشبيه الكاشير اللي بيرجّعلك الباقي. لو الباقي 87 جنيه، بيديك أكبر ورقة تنفع (50)، وبعدين أكبر ورقة تنفع من الباقي (20)، وهكذا. عمره ما بيفكر "يمكن لو اديته 20 الأول يبقى أحسن". ومع الفلوس العادية، ده دايمًا بيدّي أقل عدد ورق. ده greedy.
  1. ترتيب تنازلي عشان نبص على الأكبر الأول. b - a مش a - b.
  2. ليه >= مش >؟ لو الباقي 50 والورقة 50، لازم ناخدها. مع > هنسيبها ونكمّل بورق أصغر.
  3. ناخد الورقة ونكمّل بنفس الورقة، لأن ممكن تنفع تاني (زي 1 + 1).
  4. لو فضل باقي، يبقى الـ greedy اتزنق (مثلًا مفيش عملة 1). بنرجّع null.

6 ورقات، وده فعلًا أقل عدد. بس هل ده بيحصل مع أي عملات؟

طب إزاي تعرف إن المسألة greedy أصلًا؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

لما تشوف: maximum number ofminimum number ofcan you reachintervals / schedule assign / matchat each step choosepartition into as many as possibleconstraints up to 10⁵
ومش هو غالبًا لو: number of wayscoins بأي قيم + أقل عددsubset sum = target بالظبطn صغير (20) ومطلوب كل الاحتمالات

الـ constraints بتقول كتير: n لحد 10⁵ معناها لازم O(n log n) أو أحسن، فالـ DP بتاع O(n²) مش هيعدّي، والـ greedy مرشح قوي. ولو المطلوب "عدد الطرق"، ده عدّ، والعدّ محتاج تشوف كل الاختيارات، فده DP مش greedy.

الـ patternالفكرةمسائل
Sort then pickرتّب بالحاجة اللي بتفرق، وخد بالترتيبAssign Cookies، Non-overlapping Intervals، Arrows
Collect every gainكل مكسب محلي خده، والخسارة سيبهاStock II
Farthest reachافتكر أبعد نقطة تقدر توصلها لحد دلوقتيJump Game I و II، Partition Labels
Reset when negativeلو الحساب بقى سالب، ابدأ من جديد بعد النقطة ديGas Station، Maximum Subarray (Kadane)
flowchart TD
  A["Choose step by step?"] --> B{"Asks for number of ways?"}
  B -- yes --> D["DP"]
  B -- no --> C{"Can you find a small counterexample?"}
  C -- yes --> D
  C -- no --> E{"Can you argue: swapping in my choice never hurts?"}
  E -- yes --> G["Greedy: sort or scan once"]
  E -- no --> F["Stress test greedy vs brute force first"]
  

السؤال الأهم في النص: تقدر تلاقي counterexample؟

السؤال ده هو قلب الفصل: إزاي تتأكد إن الـ greedy صح، وإزاي تكسره لو مش صح؟

صح ولا غلط؟ الـ exchange argument والـ counterexample

اكسره الأول: counterexample

قبل ما تثبت حاجة، حاول تكسرها. خد عملات [1, 3, 4] والمبلغ 6، وشغّل نفس الكود اللي فوق:

الـ greedy خد الـ 4 لأنها أكبر حاجة، والـ 4 دي ورّطته في 1 + 1. الحل الأحسن 3 + 3، عملتين بس. يعني أحسن اختيار دلوقتي (4) مش جزء من أحسن حل. عشان كده مسألة Coin Change (322) بأي عملات محتاجة DP، وده اللي اتشرح هناك.

إزاي تدوّر على counterexample جرّب inputs صغيرة جدًا (2 أو 3 عناصر) فيها تعارض: عنصر شكله أحسن دلوقتي بس بيقفل الطريق. ولو مش لاقي، اكتب brute force وقارن بيه على آلاف inputs عشوائية صغيرة. ده بياخد دقيقتين، وبيوفّر عليك Wrong Answer.

ولو مش لاقي counterexample: الـ exchange argument

ده الإثبات اللي بيتقال في الانترفيو، وفكرته بسيطة:

  1. خد أي حل optimal (مش لازم تعرفه، بس افترض إنه موجود).
  2. لو أول اختيار فيه هو نفس اختيار الـ greedy، تمام.
  3. لو مختلف: ورّي إنك تقدر تبدّل اختياره باختيار الـ greedy، والحل يفضل valid ومش أوحش.
  4. كرر ده على كل خطوة. في الآخر الحل الـ optimal اتحوّل لحل الـ greedy من غير ما يوحش. يبقى الـ greedy optimal.
بالبلدي "أي حل حلو، أقدر أبدّل فيه اختياره باختياري من غير ما أخسر حاجة." لو تقدر تقول الجملة دي وتبررها، الـ greedy صح. في الكوينز [1, 3, 4] مش هتقدر: تبدّل 3 + 3 بـ 4 + ... هتخسر.

هتشوف الـ argument ده بيتطبّق في كل مثال محلول تحت، بجملة أو اتنين.

كل الـ greedy solutions تقريبًا ليها نفس الهيكل. يلا نكتبه مرة واحدة.

الهيكل العام

  1. نص الـ greedy problems بتبدأ بـ sort، والسؤال الحقيقي: بإيه؟ (بالـ start ولا الـ end؟ تصاعدي ولا تنازلي؟). الـ exchange argument هو اللي بيقولك.
  2. الـ state صغير دايمًا: رقم أو اتنين. لو لقيت نفسك محتاج تفتكر حاجات كتير، غالبًا ده DP.
  3. القاعدة المحلية: قرار بيتاخد بالـ item ده والـ state بس، من غير ما تبص لقدّام.
  4. مفيش undo. ده اللي بيخلّيه O(n) بعد الـ sort، وده اللي بيخلّيه يغلط لو القاعدة غلط.

الـ complexity: O(n log n) لو فيه sort، و O(n) لو scan بس، والـ memory غالبًا O(1).

أبسط تطبيق: sort الاتنين وطابق.

مثال محلول 1: Assign Cookies

Assign Cookies

easyLeetCode 455

كل طفل ليه "طمع" g[i]: مش هيرضى غير بكوكي حجمها >= g[i]. وعندك كوكيز بأحجام s[j]. كل طفل ياخد كوكي واحدة بالكتير. أكبر عدد أطفال تقدر ترضيهم؟

Input: g = [5, 2, 8, 1], s = [3, 1, 6, 2] Output: 3 (1 gets 1, 2 gets 2, 5 gets 6; nothing fits 8)

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

  1. Brute force: جرّب كل طرق التوزيع. ده exponential.
  2. الـ key insight: الطفل الأقل طمع هو الأسهل. ادّيله أصغر كوكي تكفّيه. ليه أصغر واحدة؟ عشان الكوكيز الكبيرة تفضل للأطفال الأطمع.
  3. الـ exchange argument: لو حل optimal ادّى الطفل ده كوكي أكبر، بدّلها بالأصغر اللي تكفّيه. الكبيرة رجعت متاحة، فمفيش حاجة وحشت.
  4. الخطة: رتّب الاتنين، وامشي بـ two pointers: لو الكوكي تكفّي الطفل، طابقهم. لو لأ، الكوكي دي صغيرة على كل اللي فاضلين، ارميها.
  5. الحالات الطرفية: مفيش كوكيز، كل الكوكيز صغيرة، كوكيز أكتر من الأطفال.
  1. الـ comparator لازم. [10, 9, 1].sort() بتطلع [1, 10, 9] لأنها بترتّب كنصوص.
  2. نقف لما يخلص الأطفال أو الكوكيز. الاتنين بـ < لأنهم indices.
  3. >= لأن الكوكي اللي حجمها بالظبط قد الطمع بتكفّي.
  4. الكوكي بتتحرك في الحالتين. لو اتاخدت، خلصت. لو صغيرة على الطفل ده، هتبقى صغيرة على كل اللي بعده (أطمع منه)، فنرميها.
  5. child هو عدد اللي اتطابقوا، لأنه بيزيد بس مع كل تطابق.

التعقيد: الـ sort O(n log n + m log m)، والـ loop O(n + m). الـ memory O(1) غير الـ sort.

هنا رتّبنا عشان نطابق. طب لو مفيش حاجة نرتّبها، والقرار محلي في كل يوم؟

مثال محلول 2: Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

mediumLeetCode 122

prices[i] سعر سهم في اليوم i. تقدر تشتري وتبيع كام مرة ما تحب، بس تمسك سهم واحد بالكتير في نفس الوقت. أكبر مكسب؟

Input: prices = [3, 1, 4, 8, 7, 2, 5] Output: 10 (buy 1 sell 8 = 7, buy 2 sell 5 = 3)

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

  1. الجديد هنا: مفيش sort. القرار بيتاخد يوم بيوم، وكل مكسب صغير بنلمّه.
  2. الـ key insight: لو اشتريت بـ 1 وبعت بـ 8 والسعر طالع على طول (1، 4، 8)، المكسب 8 - 1 = 7 هو نفسه (4 - 1) + (8 - 4). يعني أي صفقة على طلعة = مجموع الطلعات اليومية.
  3. فالقاعدة: كل يوم السعر فيه أعلى من امبارح، خد الفرق. كل يوم أقل، سيبه. مفيش يوم نازل ممكن يزوّد المكسب.
  4. الحالات الطرفية: يوم واحد (0)، أسعار نازلة على طول (0).
  1. ليه i = 1؟ عشان بنقارن بـ prices[i - 1]. لو بدأنا من 0 هنقرا prices[-1] وده undefined.
  2. > مش >=: يوم بنفس السعر مكسبه صفر، فمش فارقة، بس > أوضح.
  3. ده "اشتري امبارح وبيع النهارده" على كل طلعة. في الحقيقة مش لازم تعمل الصفقات دي فعلًا، المجموع بس هو اللي بيساوي.

التعقيد: O(n) وقت و O(1) memory.

ما تخلطهاش بـ Stock I في 121 مسموح صفقة واحدة بس، والحل هناك تمسك أقل سعر لحد دلوقتي (best so far). القاعدة هنا ("لم كل طلعة") هتطلع إجابة أكبر من المسموح هناك.

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

مثال محلول 3: Jump Game

Jump Game

mediumLeetCode 55

إنت واقف عند index 0. الرقم nums[i] هو أقصى عدد خطوات تقدر تنطّها لقدّام من i (تقدر تنط أقل). تقدر توصل لآخر index؟

Input: nums = [2, 0, 3, 1, 0, 4] Output: true Input: nums = [1, 2, 0, 1, 0, 3] Output: false (index 4 holds 0 and nothing reaches past it)

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

  1. الجديد هنا: بنشيل state من اللي فات: أبعد index نقدر نوصله لحد دلوقتي (farthest).
  2. Brute force: من كل index جرّب كل نطة ممكنة، recursion أو DP. ده O(n²).
  3. الـ key insight: مش محتاجين نعرف إزاي وصلنا لـ index، كفاية نعرف إنه reachable. ولو i reachable، فكل اللي قبله reachable برضه (نطيت فوقهم). يعني الـ reachable دايمًا prefix متصل [0..farthest].
  4. الخطة: امشي من الشمال. لو i > farthest يبقى اتزنقنا. غير كده كبّر الـ farthest بـ i + nums[i].
  5. الحالات الطرفية: array فيها عنصر واحد (true، إنت واقف عليه)، صفر في الأول.
  1. بنبدأ بـ 0 لأننا واقفين عند index 0، فهو reachable.
  2. > مش >=: لو i === farthest يبقى i reachable بالظبط، وينفع ننط منه.
  3. من i نقدر نوصل لحد i + nums[i]. الـ max لأن الـ farthest عمره ما بيقل.
  4. nums.length - 1 هو آخر index، مش الطول. وده early return: مش محتاجين نكمّل.

التعقيد: O(n) وقت و O(1) memory.

عرفنا نوصل ولا لأ. طب لو مضمون إننا هنوصل، والسؤال بقى: أقل عدد نطات كام؟

مثال محلول 4: Jump Game II

Jump Game II

mediumLeetCode 45

نفس الـ array، ومضمون إن آخر index ممكن توصله. أقل عدد نطات توصّلك له؟

Input: nums = [2, 1, 3, 1, 1, 2, 1] Output: 3 (0 → 2 → 5 → 6)

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

  1. الجديد هنا: نفس الـ farthest، بس بنقسم الـ array لـ windows: كل window هي الـ indices اللي توصلها بنفس عدد النطات.
  2. الـ key insight: بنطة واحدة من 0 بتوصل لـ [1..2]. بنطتين بتوصل لأي حاجة توصلها من أي index في [1..2]، يعني لحد أبعد farthest منهم. ده BFS بالظبط، كل window مستوى، بس من غير queue.
  3. الخطة: end هو آخر index في الـ window الحالية. وإحنا ماشيين بنحدّث الـ farthest. لما i يوصل end، خلصنا الـ window: نطة جديدة، والـ window الجاية بتخلص عند الـ farthest.
  4. الحالات الطرفية: عنصر واحد (0 نطات)، نطة واحدة توصل على طول.
  1. بـ 0 نطات نوصل لـ index 0 بس، فالـ window الأولى [0..0]، و end = 0.
  2. ليه nums.length - 1 مش nums.length؟ لما توصل لآخر index خلاص وصلت، مش محتاج تنط منه. لو لفيت عليه وكان i === end، هتعد نطة زيادة. جرّب [0]: الصح 0، ومع < nums.length هيطلع 1.
  3. زي Jump Game بالظبط.
  4. آخر window. أي index بعدها محتاج نطة زيادة، وأبعد حاجة نقدر نوصلها بالنطة دي هي الـ farthest اللي جمعناه من الـ window كلها.

التعقيد: O(n) وقت و O(1) memory. والـ DP البديهي O(n²).

هنا كنا بنكبّر حاجة (الـ reach). طب لو الحساب ممكن يبقى سالب، ولازم نبدأ من جديد؟

مثال محلول 5: Gas Station

Gas Station

mediumLeetCode 134

محطات بنزين على دايرة. في المحطة i بتاخد gas[i]، والطريق منها للي بعدها بيصرف cost[i]. العربية بتبدأ بتانك فاضي. من أنهي محطة تبدأ عشان تلف الدايرة كلها؟ لو مفيش رجّع -1 (والإجابة لو موجودة واحدة بس).

Input: gas = [4, 1, 2, 6, 3], cost = [3, 4, 3, 2, 4] Output: 3

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

  1. الجديد هنا: الـ state ممكن يبقى سالب، ولما يحصل ده بنعمل reset ونبدأ من جديد بعد النقطة دي.
  2. Brute force: جرّب كل محطة كبداية ولف الدايرة. O(n²).
  3. أول ملاحظة: لو مجموع البنزين أقل من مجموع الصرف، مستحيل. ولو مش أقل، فيه إجابة (المسألة بتضمن إنها واحدة).
  4. حجة الـ reset: بدأنا من start والتانك بقى سالب عند i. أي محطة بين start و i برضه هتفشل قبل i + 1: إحنا وصلنالها بتانك >= 0، فلو بدأنا منها بتانك صفر هنبقى أوحش أو زي ما إحنا. يبقى نرمي الكل ونجرّب i + 1.
  5. الحالات الطرفية: محطة واحدة، المجموع بالظبط صفر (ينفع).
  1. المكسب الصافي من المحطة دي للي بعدها. ممكن يبقى سالب.
  2. اتنين حسابات: total للدايرة كلها (هل فيه إجابة أصلًا؟)، و tank من start بس (هل الـ start ده نافع؟).
  3. < 0 مش <= 0: تانك صفر معناه وصلت بآخر نقطة بنزين، وده مسموح.
  4. i + 1 مش i. المحطة i نفسها جزء من الفشل (حجة الـ reset بتشمل start..i كلهم).
  5. ليه بنثق في start من غير ما نلف تاني؟ الـ tank من start لآخر الـ array ما بقاش سالب، واللي قبل start كان مجموعه سالب. فلو total >= 0، الجزء من start للآخر كبير كفاية يغطي العجز اللي في الأول.

التعقيد: لفة واحدة، O(n) وقت و O(1) memory.

نفس الحركة في Kadane Maximum Subarray (53) بيتحل بنفس الـ reset: لو المجموع الحالي بقى سالب، ارميه وابدأ من العنصر الجاي، لأن أي prefix سالب بيقلل أي حاجة بعده.

الـ farthest رجع تاني في المثال الجاي، بس على حروف: "الجزء ده لازم يمتد لحد فين؟".

مثال محلول 6: Partition Labels

Partition Labels

mediumLeetCode 763

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

Input: s = "abacbdeffe" Output: [5, 1, 4] ("abacb" | "d" | "effe")

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

  1. الجديد هنا: بنحسب معلومة مساعدة الأول (آخر ظهور لكل حرف)، وبعدين farthest reach عليها.
  2. الـ key insight: لو الجزء بدأ بـ a، لازم يمتد على الأقل لحد آخر a. وكل حرف جوه الجزء ده بيفرض نفس الحاجة: الجزء لازم يوصل لآخر ظهور ليه. فالـ end بيكبر كل ما نقابل حرف آخر ظهوره أبعد.
  3. إمتى نقطع؟ لما i يوصل للـ end. ساعتها كل حرف شفناه آخر ظهور ليه جوه الجزء، فالقطع آمن. وبنقطع أول ما ينفع عشان نطلّع أكبر عدد أجزاء.
  4. الحالات الطرفية: حرف واحد، كل الحروف مختلفة (كل واحد جزء)، string كله حرف واحد متكرر (جزء واحد).
  1. لفة أولى: كل حرف بيكتب الـ index بتاعه فوق اللي قبله، فاللي بيفضل هو آخر ظهور.
  2. نفس farthest = Math.max(...) بتاعة Jump Game، بس الـ reach هنا هو آخر ظهور للحرف.
  3. i === end: وصلنا للحد اللي كل اللي جوه محتاجينه، يبقى نقطع.
  4. + 1 لأننا بنعدّ عناصر: الجزء من index 0 لـ 4 فيه 5 حروف. ده عكس الـ width في Container With Most Water اللي كان مسافة.
  5. الجزء الجاي بيبدأ بعد القطع على طول.

التعقيد: لفتين، O(n) وقت. الـ memory O(1) لأن الحروف 26 بس.

آخر مثال بيرجع للـ sort، بس السؤال الصعب فيه: نرتّب بإيه؟

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

Non-overlapping Intervals

mediumLeetCode 435

عندك intervals [start, end]. أقل عدد تشيله عشان الباقي ما يتداخلش؟ اللي بيلمسوا بعض بس ([1, 2] و [2, 3]) مش متداخلين.

Input: intervals = [[1,4],[2,3],[3,6],[5,7],[6,8]] Output: 2 (remove [1,4] and [5,7])

شفنا المسألة دي في فصل الـ intervals. هنا هنبص عليها من زاوية الـ greedy: ليه الترتيب بالـ end بالذات صح؟

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

  1. الجديد هنا: الـ sort مش واضح. اختيار المفتاح الغلط (الـ start أو الطول) بيدّي إجابة غلط، والـ exchange argument هو اللي بيختار.
  2. اقلبها: أقل عدد نشيله = n ناقص أكبر عدد نسيبه من غير تداخل.
  3. الـ key insight: أول interval نسيبه لازم يبقى اللي بيخلص بدري. ليه؟ عشان بيسيب أكبر مساحة للباقيين.
  4. الـ exchange argument: أي حل optimal، أول interval فيه بيخلص عند e. اللي بيخلص بدري (e' <= e) ينفع ياخد مكانه: كل اللي بعده كانوا بيبدأوا بعد e، فأكيد بعد e'. نفس العدد، مفيش خسارة.
  5. الخطة: رتّب بالـ end، وامشي: لو الـ interval بيبدأ بعد آخر end سبناه (أو عنده)، سيبه. لو لأ، شيله.
  1. الترتيب بالـ end (a[1])، مش بالـ start. ده القرار كله.
  2. -Infinity عشان أول interval يتساب دايمًا مهما كان الـ start بتاعه (حتى لو سالب).
  3. >= مش >: اللي بيلمسوا بس مش متداخلين. [1, 2] و [2, 3]: 2 >= 2 فنسيب الاتنين.
  4. بيتداخل مع آخر واحد سبناه. واللي سبناه بيخلص قبله أو معاه (بسبب الترتيب)، فشيل الجديد أحسن.

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

التعقيد: الـ sort O(n log n)، والـ loop O(n).

في الانترفيو بعد ما تكتب الـ sort، قول الجملة: "لو حل optimal بدأ بـ interval تاني، أقدر أبدّله باللي بيخلص بدري من غير ما أخسر حاجة". دي الـ exchange argument في سطر، وهي اللي بتفرق بينك وبين حد حافظ الحل.

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

غلطات مشهورة

1. greedy من غير ما تحاول تكسره

قبل ما تكتب أي greedy، جرّب 2 أو 3 inputs صغيرة فيها تعارض. لو لقيت counterexample، روح DP.

2. ترتّب بالمفتاح الغلط

الـ interval اللي بيبدأ بدري ممكن يكون طويل جدًا ويقفل الطريق. اللي بيخلص بدري هو اللي بيسيب مساحة. (فيه حل صح بالـ start بس لما يحصل تداخل لازم تسيب اللي بيخلص بدري منهم، وده أعقد.)

3. Jump Game II بتلف لحد آخر index

لما توصل لآخر index، مش محتاج تنط منه. اسأل نفسك عن كل loop: هل آخر عنصر محتاج نفس المعاملة؟

4. Gas Station: الـ reset لـ i بدل i + 1

التانك بقى سالب بعد ما صرفنا cost[i]، يعني المحطة i جزء من الرحلة الفاشلة. البداية الجديدة لازم تبقى بعدها.

5. sort() من غير comparator

نص مسائل الـ greedy بتبدأ بـ sort، فالغلطة دي بتبوّظ الحل كله من أول سطر. مع أرقام أقل من 10 الـ test هيعدّي بالصدفة، فخلي بالك.

6. off-by-one في الأطوال

عدّ العناصر من start لـ end (الاتنين داخلين) = end - start + 1. المسافة بينهم = end - start. اسأل نفسك: بعدّ ولا بقيس؟

دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.

اختبر نفسك

عملات [1, 5, 6, 9] والمبلغ 11. الـ greedy (أكبر عملة الأول) هيستخدم كام عملة، والأحسن كام؟

  • الاتنين 2
  • الـ greedy 3 (9 + 1 + 1)، والأحسن 2 (5 + 6)
  • الـ greedy 2، والأحسن 3
  • الـ greedy هيتزنق ويرجّع -1

الـ 9 شكلها أحسن اختيار، بس بتسيب 2 ومفيش غير 1 + 1. ده counterexample تاني لـ Coin Change بالـ greedy.

في Non-overlapping Intervals، نرتّب بإيه عشان الـ greedy يبقى صح؟

  • بالـ start تصاعدي
  • بالـ end تصاعدي
  • بالطول من الأقصر
  • مش فارقة

اللي بيخلص بدري بيسيب أكبر مساحة للباقيين، وأي حل optimal تقدر تبدّل أول interval فيه بيه من غير خسارة. الأقصر مش كفاية: interval قصير ممكن يقع في نص اتنين طوال ويبوّظهم الاتنين.

Gas Station: مجموع gas هو 9 ومجموع cost هو 10. الإجابة؟

  • 0
  • المحطة اللي فيها أكبر gas
  • -1 من غير ما تلف أصلًا
  • محتاج تجرّب كل محطة

البنزين كله أقل من الصرف كله، فمهما بدأت منين مش هتكمّل الدايرة. ده الـ total >= 0 في آخر الكود.

Stock II على [5, 4, 3, 2, 1]. المكسب؟

  • 0
  • 4
  • -4
  • 1

مفيش ولا يوم السعر طلع فيه، فمفيش ولا فرق يتلم. والمكسب عمره ما يبقى سالب: لو مفيش صفقة كويسة، ما تعملش صفقات.

في Jump Game، ليه farthest لوحده كفاية ومش محتاجين نعرف إزاي وصلنا لكل index؟

  • عشان الـ array مترتبة
  • عشان الـ reachable دايمًا prefix متصل [0..farthest]، فرقم واحد بيوصفه كله
  • عشان كل نطة طولها 1
  • مش كفاية، محتاجين DP

لو وصلت لـ index، يبقى عدّيت على أو فوق كل اللي قبله، وكلهم reachable. فمفيش فراغات، والـ farthest هو كل المعلومة.

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

Minimum Number of Arrows to Burst Balloons

mediumLeetCode 452

كل بالونة interval أفقي [start, end]. سهم رأسي عند x بيفرقع كل بالونة فيها start <= x <= end. أقل عدد أسهم يفرقع الكل؟

[[1,5],[2,4],[6,9],[3,7],[8,10]] → 2 (one arrow at 4, one at 9)
تلميح 1

دي أخت 435. البالونة اللي بتخلص بدري لازم سهم يفرقعها في وقت ما قبل نهايتها. فين أحسن مكان للسهم ده؟

تلميح 2

رتّب بالـ end. اضرب أول سهم عند نهاية أول بالونة: أبعد مكان لسه بيفرقعها، فبيلحق أكبر عدد بالونات بعدها. أي بالونة الـ start بتاعها <= مكان السهم اتفرقعت. أول واحدة بعده محتاجة سهم جديد عند نهايتها.

الحل

لاحظ start > pos هنا مش >=: لو البالونة بتبدأ عند مكان السهم بالظبط، السهم فرقعها (اللمس هنا بيتحسب). ده عكس 435 اللي اللمس فيها مش تداخل. نفس الكود تقريبًا، والفرق في حرف واحد جاي من نص المسألة. O(n log n).

لو الأسئلة عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

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

في كل مسألة، قبل ما تكتب، قول لنفسك الـ exchange argument في جملة، أو دوّر على counterexample دقيقتين. لو قعدت أكتر من 25 دقيقة، ارجع للمثال اللي شبهها.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الـ greedy بياخد أحسن اختيار دلوقتي ومبيرجعش فيه. بيبقى صح لما تقدر تقول: "أي حل optimal أقدر أبدّل فيه اختياره باختياري من غير خسارة"، وبيبقى غلط لما counterexample صغير يكسره.
السؤالالإجابة
greedy ولا DP؟جرّب counterexample صغير. لو لقيت، DP. لو المطلوب "عدد الطرق"، DP.
إزاي أثبت؟exchange argument: أبدّل أول اختيار في أي حل optimal باختياري من غير خسارة.
أرتّب بإيه؟بالحاجة اللي بتسيب أكبر مساحة للباقي (غالبًا الـ end في الـ intervals).
Complexity؟O(n log n) لو فيه sort، O(n) لو scan، و O(1) memory غالبًا.
الـ off-by-one المشهورة؟n - 1 في Jump II، و + 1 في الأطوال، و i + 1 في الـ reset.

الفصل الجاي: آخر أداة في الدليل: Bit Manipulation. بدل ما تتعامل مع الرقم كقيمة، هتتعامل مع الـ 0 و 1 اللي جواه، ومسائل كانت محتاجة hash map أو loop هتتحل في سطر.