طول اتحاد فترات: دمج التداخل والتماس دون تكرار الأجزاء

الطول المغطى يختلف من مجموع الأطوال

إذا كانت لدينا فترات على خط واحد، يمكن جمع طول كل فترة منفردة، ويمكن قياس طول الجزء الذي تغطيه جميعها مرة واحدة. السؤالان لا يعطيان بالضرورة العدد نفسه؛ فالجزء الذي يدخل فترتين يحسب مرتين في الجمع المباشر، لكنه يبقى جزءًا واحدًا من الاتحاد. نريد في هذا المقال الطول المغطى، مع بيان الفجوات التي لا تغطيها أي فترة.

يعرض CP-Algorithms حساب طول اتحاد القطع بواسطة نهايات مرتبة وعدد تغطية نشط. وتوضح وثائق Boost ICL أن جمع الفترات يمكن أن يدمج المتداخل والمتلامس أو يحفظ حدودًا أكثر في التمثيل. نستعمل هاتين الفكرتين المعروفتين، بينما الفترات والأعداد والرسوم والفحوص التالية مؤلفة للمقال، دون نقل مثال المصدر أو كوده أو تشغيل مكتبته.

سنرتب فترات نصف مفتوحة وننتج أجزاء متصلة مدمجة، ثم نراجع طولها بطريقة أخرى تعد التغطية بين النهايات. الأمثلة إحداثيات تعليمية بوحدة طول واحدة، وليست مواعيد عمل أو قياسات مواقع أو كميات استهلاك. لا نقرر أن جمع الأطوال خطأ في كل استخدام؛ نحدد أن السؤال هنا عن جزء مغطى مرة واحدة، لا عن مجموع مساهمات مدخلات مستقلة.

مرجع الطول وعد التغطية، مرجع أنماط دمج الفترات.

حد البداية مشمول والتوقف غير مشمول

نكتب الفترة من a إلى b مع شمول البداية واستبعاد التوقف. مثلًا [1,5) تغطي المواضع من واحد حتى ما قبل خمسة، وطولها أربعة. لا نضيف وحدة إلى فرق الطرفين لأننا لا نعد قائمة نقاط صحيحة مغلقة الطرفين. محورنا مستمر، والنهايات الصحيحة مجرد اختيار يجعل مراجعة الأطوال وفحوص الخلايا الوحدية سهلة.

الفترة [6,6) فارغة في هذا العقد وطولها صفر، لذلك لا تضيف جزءًا إلى الاتحاد. وإذا تلامست [1,5) و[5,8)، فإن الخمسة التي تستبعدها الأولى تبدأ بها الثانية، فتغطيان معًا [1,8) دون فجوة. لا نحتاج تداخلًا ذا طول موجب كي نعرض تغطيتهما جزءًا متصلًا واحدًا.

أما الفترة المغلقة ذات طرفين متساويين فتمثل نقطة واحدة، وليست مجموعة فارغة، لكن طول النقطة على الخط يظل صفرًا. نذكر الفرق كي لا ننسب التمثيل نصف المفتوح إلى كل أنواع الفترات. سؤال العضوية في نقطة طرفية قد يتغير مع شمول الطرف، بينما قياس طول امتداد محدود لا يحصل على طول موجب من نقطة واحدة.

ست فترات من السالب إلى الموجب

قائمة الأصل هي [-2,3) ثم [1,5) ثم [5,8) ثم [10,12) ثم [11,14) ثم [6,6). أطوالها خمسة وأربعة وثلاثة واثنان وثلاثة وصفر، ومجموعها سبعة عشر. الإحداثي السالب في البداية لا يجعل الطول سالبًا؛ نحسب النهاية ناقص البداية مع ترتيب الطرفين كما أعلنناه.

تتداخل الفترة الأولى والثانية بين واحد وثلاثة، بطول اثنين. وتتداخل الرابعة والخامسة بين أحد عشر واثني عشر، بطول واحد. والثانية والثالثة تتلامسان عند خمسة دون تداخل ذي طول. في هذه القائمة يفسر تكرار الجزأين المذكورين الفرق بين الجمع المباشر والطول المغطى الذي سنصل إليه، وهو أربع عشرة وحدة.

الرسم الرئيسي يعرض صفًا لكل فترة وصفًا للاتحاد بعد الدمج. لا نقرأ عدد الصفوف بوصفه طولًا، ولا نقيس الصورة بدل استعمال الإحداثيات المكتوبة. الفترة الفارغة السادسة لا تحصل على شريط ممتد؛ علامتها تذكير بمدخل لا يضيف تغطية. ونحفظ القائمة الأصلية حتى نفهم لماذا كان المجموع الخام سبعة عشر رغم أن التمثيل المدمج سيحتوي جزأين فقط.

رتب البدايات واحتفظ بأبعد توقف

نستبعد الفترات الفارغة من الدمج، ثم نرتب الباقي بحسب البداية. نبدأ بجزء جارٍ هو [-2,3). حين نصل إلى [1,5)، نجد بدايتها داخل الجزء الجاري، فنمد توقفه إلى خمسة. صار الجزء [-2,5)، ولم نضف طول الفترة الثانية كله مرة أخرى؛ حفظنا اتحادها مع الجزء السابق بدل جمع مساهمتها منفردة.

بعد ذلك تأتي [5,8)، وبدايتها تساوي توقف الجزء الجاري. نضمها وفق عقد التماس، فيصبح الجزء [-2,8). عندما تأتي [10,12)، تبدأ بعد ثمانية، فتوجد فجوة غير مغطاة ونثبت الجزء الأول كما هو. نبدأ جزءًا جديدًا [10,12)، ثم تمده [11,14) إلى [10,14). النهاية تعطي هذين الجزأين المفصولين.

في كل دمج نأخذ الأكبر بين التوقف القديم والجديد. لو كان الجزء [0,10) وجاءت [2,3) داخله، فلا نخفض النهاية من عشرة إلى ثلاثة. الفترة الصغيرة لا تلغي تغطية الأكبر. هذا التفصيل يمنع اختصارًا خاطئًا يكتب نهاية كل مدخل على الجزء الجاري دون مراجعة، ويشرح لماذا يصبح احتواء فترة أخرى دمجًا بلا تغيير في الامتداد.

التماس يغير التمثيل ولا يضاعف الطول

الفترتان [1,4) و[4,6) يمكن عرضهما جزأين متجاورين أو جزءًا واحدًا [1,6). في الحالتين الطول خمسة، لأن نقطة الاتصال لم تضف امتدادًا جديدًا. اخترنا في تنفيذنا جمع المتلامس كي يكون التمثيل المدمج مختصرًا، لكن عدد الأجزاء الناتجة يتعلق بهذه السياسة، ولا نستعمله وحده قياسًا للطول.

توضح وثائق Boost أنماط دمج أو فصل أو تقسيم تحفظ المجموعة المغطاة مع حدود مختلفة في التمثيل. لا ننقل مثال المكتبة هنا، ولا ندعي تشغيلها على بياناتنا. الفكرة التي نستفيد منها أن عدد القطع المخزنة قد يختلف دون تغيير التغطية نفسها، وأن الاحتفاظ بحد أصلي قد يكون مطلوبًا لسؤال آخر غير الطول الإجمالي.

في أصلنا، [1,5) و[5,8) تتصلان بهذا الشكل، ثم تندمجان أيضًا مع تغطية [-2,3). التوقف عند خمسة يظل معلومة موجودة في المدخلات، لكنه لا يظهر حدًا بين جزأين في النتيجة المختصرة. إذا احتجنا معرفة من غطى كل جزء، نحفظ بيانات أخرى أو تمثيلًا مقسمًا، بدل افتراض أن اختفاء الحد من الاتحاد حذف وقوع الفترة الأصلية.

فجوة من ثمانية إلى عشرة

بعد الدمج، الجزء الأول من سالب اثنين إلى ثمانية طوله عشرة، والثاني من عشرة إلى أربعة عشر طوله أربعة. المجموع أربع عشرة وحدة. الفراغ بين ثمانية وعشرة طوله اثنان ولا تضيفه أي فترة. لذلك لا نكتفي بأصغر بداية وأكبر توقف ونطرح أحدهما من الآخر؛ هذا سيقيس الامتداد المحيط بما فيه الفجوة.

الامتداد من سالب اثنين إلى أربعة عشر طوله ستة عشر، وهو أكبر من طول الاتحاد بأثر الفجوة اثنين. هذا مثال واضح على أن الغلاف المحيط ليس المجموعة المغطاة نفسها. ومثلما لا يساوي مجموع الأطوال الخام سبعة عشر طول الاتحاد، فإن فرق الطرفين الخارجيين ستة عشر لا يساويه أيضًا في وجود جزء غير مغطى بينهما.

كذلك لا يساوي عدد الجزأين النهائيين أربع عشرة؛ الأول عدد تمثيلات متصلة والثاني طول بوحدة المحور. إذا غيرنا وحدات الطول أو سياسة حفظ حدود التماس، نراجع معنى الرقم الذي نعرضه. يمكن أن يبقى العدد اثنين مع تضاعف جميع الأطوال، أو يتغير عدد القطع الممثلة مع بقاء الطول نفسه في سياسة تقسيم مختلفة.

عد التغطية بين النهايات

نراجع الاتحاد بطريقة ثانية. نجمع إحداثيات النهايات المرتبة، ونحفظ عدد الفترات التي تغطي الفراغ بين نهاية والتي تليها. في أصلنا النهايات المهمة هي سالب اثنين وواحد وثلاثة وخمسة وثمانية وعشرة وأحد عشر واثنا عشر وأربعة عشر. لا نضيف نهاية الستة من الفترة الفارغة، لأنها لم تدخل التغطية في عقدنا.

بين سالب اثنين وواحد يغطي الجزء فترة واحدة، فنضيف طول ثلاثة. وبين واحد وثلاثة توجد فترتان نشطتان، لكن نضيف طول اثنين مرة واحدة. ومن ثلاثة إلى خمسة توجد واحدة بطول اثنين، ومن خمسة إلى ثمانية واحدة بطول ثلاثة. أما من ثمانية إلى عشرة فعدد التغطية صفر، ولذلك مساهمته صفر رغم أن فراغه طوله اثنان.

بعد عشرة نضيف واحدًا حتى أحد عشر، ثم واحدًا حتى اثني عشر رغم وجود فترتين نشطتين، ثم اثنين حتى أربعة عشر. مساهمات الأجزاء المغطاة هي ثلاثة واثنان واثنان وثلاثة وواحد وواحد واثنان، ومجموعها أربعة عشر. العدد النشط يقرر هل نضيف طول الفراغ، ولا يضرب هذا الطول في عدد الفترات إذا كان السؤال عن الاتحاد.

عرض الرسم بالحجم الكامل

نهايات متساوية لا تخلق امتدادًا

عند خمسة تنتهي [1,5) وتبدأ [5,8). يمكن جمع أحداث الإحداثي نفسه ثم الانتقال إلى الإحداثي التالي. عدد الفترات النشطة قبل خمسة وبعدها يظل واحدًا في هذا الجزء من المثال، مع تغير هوية الفترة التي تغطيه. لا نضيف مسافة بين نسختين من الإحداثي خمسة لأن الفرق بينهما صفر.

في مراجعة الأحداث حسبنا مساهمة الفراغ السابق بما كان نشطًا فيه، ثم حدثنا عدد التغطية عند الإحداثي الجديد. هذا الترتيب يربط كل طول بالجزء الذي غطته الفترات فعلًا. لا نقرأ حالة ما بعد النهاية لإعادة الحكم على الفراغ الذي انتهى قبلها؛ وإلا قد نحذف طولًا عند انغلاق آخر فترة رغم أنه كان مغطى حتى ذلك الحد.

قد تختلف سياسة ترتيب حدث بداية وحدث نهاية عند الإحداثي نفسه إذا كان السؤال عن عضوية تلك النقطة أو نشاطها. أما طول الفراغ بين إحداثيين مختلفين فيحتاج حالة التغطية على ذلك الفراغ، ولا ينشئ طولًا موجبًا من ترتيب الأحداث المتساوية وحدها. نبقي نوع الفترات وسؤال الطول معلنين حتى لا تنتقل نتيجة المراجعة إلى عقد عد آخر.

ثلاث فترات تكشف طرحًا ناقصًا

نختار مثالًا مستقلًا: [0,5) و[1,4) و[2,3). مجموع الأطوال تسعة، والاتحاد هو [0,5) بطول خمسة. إذا حاولنا إصلاح التكرار بطرح أطوال جميع التقاطعات الثنائية فقط، نطرح ثلاثة وواحدًا وواحدًا، فنحصل على أربعة. هذا ليس طول الاتحاد في المثال، لأن الجزء بين اثنين وثلاثة دخل التغطية ثلاث مرات.

في هذا الجزء الثلاثي، الجمع الأول حسب الوحدة ثلاث مرات، ثم طرحها ضمن الأزواج الثلاثة جعل مساهمتها صفرًا بدل واحد. نحتاج إعادتها مرة في صيغة الاستبعاد والضم لهذا المثال، فيصبح تسعة ناقص خمسة زائد واحد مساويًا خمسة. الدمج أو عد التغطية الموجب يتجنب بناء كل هذه التقاطعات التي تكبر مع عدد الفترات.

لا نعمم حساب إصلاح زوجين في القائمة الأولى إلى قاعدة تطرح كل تداخل ثنائي في أي قائمة. وجود فترة محتواة أو تكرار أكثر من مدخل قد يزيد مرات التغطية، ويحتاج المعنى نفسه: عد طول الجزء مرة إذا كان مغطى أصلًا. نراجع مثال التداخل الثلاثي كي لا يبدو توافق طرح اثنين وواحد من السبعة عشر برهانًا لطريقة غير مكتملة.

التكرار وإعادة الترتيب

إذا أعدنا إدراج الفترة [-2,3) مرة ثانية، يزيد المجموع الخام بخمسة من سبعة عشر إلى اثنين وعشرين. لكن الاتحاد لا يحصل على جزء جديد، فيبقى طوله أربعة عشر وحدوده المدمجة نفسها. هذه نتيجة لسؤال التغطية، لا قرار أن السجل المكرر يجب حذفه من أي ملف؛ قد يحمل المدخلان معنيين آخرين يحتاجهما استخدام مختلف.

وإعادة ترتيب القائمة لا تغير اتحادها. تنفيذنا يرتب نسخة من الفترات غير الفارغة ولا يغير مدخل المستخدم في موضعه، ثم يراجع التداخل بحسب بداياتها. لذلك لا نعتمد على أن الفترة التالية في الأصل تقع يمين السابقة. قد تكون أول فترة في الملف متأخرة على المحور، ويظل فرز البداية جزءًا لازمًا للطريقة التي شرحناها.

أما تعديل حدود فترة أو إضافة جزء يغطي الفجوة بين ثمانية وعشرة فيغير المجموعة نفسها، ويحتاج نتيجة تخص النسخة الجديدة. لا نستنتج صلاحية قائمة الدمج القديمة من بقاء عدد المدخلات أو المجموع الخام قريبًا من السابق. حفظ نسخة الحدود يساعد على تفسير ما تغير في التغطية وما تغير فقط في ترتيب عرض المدخلات.

السالب والفارغ والحدود المقلوبة

الإحداثيات السالبة مسموحة في أمثلتنا، لأنها مواضع على محور، وليست أطوالًا سالبة. الفترة التي تبدأ بسالب اثنين وتتوقف عند ثلاثة طولها خمسة. نحتاج أن تكون البداية أصغر من التوقف أو مساوية له. تنفيذ الفحص يرفض زوجًا مثل ثلاثة واثنين، بدل أخذ فرق مطلق وإخفاء أن ترتيب الطرفين خالف العقد الذي اخترناه.

الفترات الفارغة ذات البداية والتوقف نفسيهما لا تضيف طولًا، والقائمة الفارغة تعطي اتحادًا فارغًا وطولًا صفرًا. ومع هذا، طول صفر لا يثبت أن أي وصف لمجموعة مغلقة لا يحمل نقطة؛ قد تكون هناك نقاط منفردة بطول صفري في عقد آخر. هنا حددنا فترات نصف مفتوحة حتى يكون الاستبعاد والدمج ومعنى الفراغ صريحًا.

قبل حساب الطول، نوحد وحدة المحور؛ لا نجمع حدًا يقرأ بالمتر مع آخر بالثانية أو بمقياس مختلف على أنهما موضعان في خط واحد. فحوصنا تقبل نهايات صحيحة معلنة، وترفض النوع المنطقي أو العشري في العقد البرمجي التعليمي. لا يمنع ذلك استعمال فترات حقيقية أخرى رياضيًا، لكنه يحدد ما اختبرناه وما يحتاج تنفيذًا مناسبًا لنوعه.

نقل المحور وتكبير الأطوال

نضيف تسع وحدات إلى كل نهاية في القائمة الأصلية. يتحول الاتحاد إلى [7,17) و[19,23)، ويبقى طوله عشرة زائد أربعة، أي أربعة عشر. تغيرت الإحداثيات، لكن فروق الأطراف والفجوة والتداخل لم تتغير. هذا نقل معلوم لجميع البيانات على المحور، وليس تغييرًا لفترة واحدة ثم مقارنة النتيجة بحدود بقي بعضها قديمًا.

وعند ضرب النهايات كلها في اثنين، يصبح الاتحاد [-4,16) و[20,28)، بطولين عشرين وثمانية، ومجموع ثمانية وعشرين. بقيت الفترة الفارغة فارغة، وبقي عدد الجزأين النهائيين اثنين. الطول تضاعف لأنه تغير مقياس الأشكال على المحور نفسه؛ لا نقول إن عدد الفترات تضاعف أو إن هوية المدخلات الجديدة تحددت من الطول وحده.

إذا كانت وحدة الرسم تمثل طولًا ماديًا معينًا، نكتب هذا التفسير بجانب الناتج. تغيير قيمة الوحدة قد يغير التعبير العددي بوحدة أخرى دون تغيير الجزء الواقعي، بينما تكبير الإحداثيات في التجربة يصف بيانات جديدة على مقياس ثابت. نميز الأمرين قبل قراءة رقم أربعة عشر أو ثمانية وعشرين كأنه نتيجة مقارنة واحدة بلا تعريف للمحور.

قياس الاتحاد يختلف من اختيار جدول

قد نريد في مهمة أخرى اختيار أكبر عدد من الفترات دون تداخل على مورد واحد. عندئذ نرفض بعض الفترات كي تكون المختارات متوافقة، ولا ندمجها إلى نطاق يمثل جميع المدخلات. أما طول الاتحاد فيأخذ كل تغطية أصلية، سواء تداخلت الفترات أم لم تتداخل، ويحسب الجزء الذي غطته مرة واحدة. اسم الفترة وحده لا يحدد أي الهدفين نريد.

كما أن التمثيل المدمج [-2,8) لا يعيد وحده قائمة الفترات التي صنعته. ربما جاء من فترة واحدة ممتدة أو من فترات متداخلة ومتلامسة كما في أصلنا. إذا احتجنا معرفة عدد المصادر أو هويتها أو درجة التغطية عند كل جزء، نحفظ القائمة الأصلية أو خريطة تغطية إضافية. الطول الإجمالي أربعة عشر لا يتضمن هذه المعلومات تلقائيًا.

لذلك نكتب بطاقة نتيجة: نوع الحدود ووحدة المحور وقائمة الأصل، ثم الأجزاء المدمجة والطول المغطى، مع تمييز المجموع الخام إذا عرضناه للمقارنة. لا نسمي طول الاتحاد عدد حجوزات أو عبء عمل أو كمية مستهلكة بلا تعريف يربطها بالتغطية. ما حسبناه امتداد واحد لمجموعة فترات معلنة، وتفسيره العملي يحتاج سؤالًا آخر وبياناته المناسبة.

تحقق مستقل بخلايا وحدية

لأن نهايات فحوصنا صحيحة، قسمنا المحور إلى أجزاء وحدية من k إلى ما قبل k زائد واحد. كل جزء طوله واحد، ونحفظه مرة إذا غطته أي فترة. نقارن عدد هذه الأجزاء بطول الدمج، ونقارن مجموعة الأجزاء المغطاة قبل الدمج وبعده. هذه طريقة مستقلة عن فرز البدايات، وتتحقق من التغطية نفسها لا من رقم الطول وحده.

راجعنا 9724 قائمة مرتبة من صفر إلى ثلاث فترات، بنهايات صحيحة من سالب اثنين إلى ثلاثة، مع جميع أزواج البداية والتوقف الصالحة في هذا المجال. شملت القوائم الفارغ والتكرار والاحتواء والتماس والتداخل الثلاثي. قارنا كذلك طول مراجعة الأحداث بالخلايا الوحدية، وتأكدنا من أن النتيجة المدمجة أجزاء موجبة الطول بينها فجوات فعلية وفق سياستنا.

وراجعنا مثال السبعة عشر والأربعة عشر، والنقل والتكبير والمدخل المخالف. هذه تجارب محدودة وليست برهانًا تجريبيًا لجميع أنواع النهايات أو قياس أداء أو تشغيلًا لمكتبة المصدر. قبل اعتماد نتيجة جديدة، ثبت سؤال الطول والحدود والوحدة، ثم ادمج أو راجع التغطية بين النهايات وقارن مثالًا صغيرًا يدويًا. ستعرف لماذا لا تضرب الطول في عدد التغطيات، وما الذي تحفظه الأجزاء المختصرة وما الذي يبقى بحاجة إلى سجل الأصل.