فترات الدمج


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ سيسكو يباي Facebook جولدمان ساكس جوجل IXL Microsoft أوراكل بالانتير تكنولوجيز Paypal Splunk مربع تويتر اوبر في إم وير مختبرات وول مارت ياهو ياندكس
مجموعة فرز

في مشكلة دمج الفترات ، أعطينا مجموعة من الفترات من الشكل [l ، r] ، دمج الفترات المتداخلة.

أمثلة

إدخال
{[1 ، 3] ، [2 ، 6] ، [8 ، 10] ، [15 ، 18]}
الناتج
{[1 ، 6] ، [8 ، 10] ، [15 ، 18]}

فترات الدمج

إدخال
{[1، 4]، [1، 5]}
الناتج
{[1]}

نهج ساذج لدمج الفترات

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

كود مزيف

لنفترض أن l [] تمثل الحد الأدنى (نقطة البداية) لجميع الفترات و r [] تمثل الحد الأعلى (نقطة النهاية) لجميع الفواصل الزمنية.

int n = total number of intervals
for (int i = 0; i < n; i++) {
  // Removed interval
  if (l[i] == -infinity && r[i] == -infinity) {
    continue;
  }
  for (int j = 0; j < n; j++) {
    // Do not compare with itself
    if (i == j)
      continue;
    // Do not compare with removed intervals
    if (l[i] == infinity && r[i] == -infinity) {
      continue;
    }
    // Check if there is some intersection point	
    if ((l[j] >= l[i] && l[j] <= r[i]) || (r[j] >= l[i] && r[j] <= r[i])) {
      // Merge the intervals
      l[i] = min(l[i], l[j])
      r[i] = min(r[i], r[j])
      // Remove the other interval
      l[j] = -infinity
      r[j] = -infinity
    } else {
      // Do not merge
    }
  }
}
// Print the merged intervals
for (int i = 0; i < n; i++) {
  if (!(l[i] == -infinity && r[i] == -infinity)) {
    print(l[i] + " " + r[i]);
  }
}

تعقيد الوقت = O (ن ^ 2) حيث n هو عدد الفترات المعطاة. نتحقق هنا من كل زوج من الفاصل الزمني الذي يستغرق وقتًا N * N.

كود جافا

public class MergingIntervals {
    // Function to merge the intervals and print merged intervals
    private static void mergeIntervals(Interval intervals[]) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            // Removed intervals
            if (intervals[i].l == Integer.MIN_VALUE
                    && intervals[i].r == Integer.MIN_VALUE) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                // Do not compare with itself
                if (i == j)
                    continue;
                // Do not compare with removed intervals
                if (intervals[i].l == Integer.MIN_VALUE
                        && intervals[i].r == Integer.MIN_VALUE) {
                    continue;
                }
                // Check if there is some intersection point
                if ((intervals[j].l >= intervals[i].l && intervals[j].l <= intervals[i].r) ||
                        intervals[j].r >= intervals[i].l && intervals[j].r <= intervals[i].r) {
                    // Merge the intervals
                    intervals[i].l = Math.min(intervals[j].l, intervals[i].l);
                    intervals[i].r = Math.max(intervals[j].r, intervals[i].r);
                    // Remove the other interval
                    intervals[j].l = Integer.MIN_VALUE;
                    intervals[j].r = Integer.MIN_VALUE;
                } else {
                    // Do not merge
                }
            }
        }

        // Print the merged intervals
        for (int i = 0; i < n; i++) {
            if (!(intervals[i].l == Integer.MIN_VALUE && intervals[i].r == Integer.MIN_VALUE)) {
                System.out.println(intervals[i].l + " " + intervals[i].r);
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        Interval intervals[] = new Interval[4];
        intervals[0] = new Interval(1, 3);
        intervals[1] = new Interval(2, 6);
        intervals[2] = new Interval(8, 10);
        intervals[3] = new Interval(15, 18);

        mergeIntervals(intervals);

        // Example 2
        Interval intervals2[] = new Interval[2];
        intervals2[0] = new Interval(1, 4);
        intervals2[1] = new Interval(1, 5);

        mergeIntervals(intervals2);
    }

    // Class representing an interval
    static class Interval {
        int l;      // Staring point
        int r;      // Ending point

        public Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }

        // Comparator to sort the intervals
        public static final Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                int l1 = o1.l;
                int l2 = o2.l;
                int r1 = o1.r;
                int r2 = o2.r;

                if (l1 == l2) {
                    return Integer.compare(r1, r2);
                }

                return Integer.compare(l1, l2);
            }
        };
    }
}

كود C ++

#include <bits/stdc++.h>
using namespace std;

// Structure representing an interval
struct Interval {
    int l, r;
};

// Function to merge the intervals and print merged intervals
void mergeIntervals(Interval intervals[], int n) {
    for (int i = 0; i < n; i++) {
        // Removed intervals
        if (intervals[i].l == INT_MIN && intervals[i].r == INT_MIN) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            // Do not compare with itself
            if (j == i) {
                continue;
            }
            // Do not compare with removed intervals
            if (intervals[i].l == INT_MIN && intervals[i].r == INT_MIN) {
                continue;
            }
            // Check if there is some intersection point
            if ((intervals[j].l >= intervals[i].l && intervals[j].l <= intervals[i].r) || (intervals[j].r >= intervals[i].l && intervals[j].r <= intervals[i].r)) {
                // Merge the intervals
                intervals[i].l = std::min(intervals[i].l, intervals[j].l);
                intervals[i].r = std::max(intervals[i].r, intervals[j].r);
                // Remove the other interval
                intervals[j].l = INT_MIN;
                intervals[j].r = INT_MIN;
            } else {
                // Do not merge
            }
        }
    }
    
    // Print the merged intervals
    for (int i = 0; i < n; i++) {
        if (!(intervals[i].l == INT_MIN && intervals[i].r == INT_MIN)) {
            cout<<intervals[i].l<<" "<<intervals[i].r<<endl;
        }
    }
}

int main() {
    // Example 1
    Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    
    int n1 = sizeof(intervals) / sizeof(intervals[0]);

    mergeIntervals(intervals, n1);

    // Example 2
    Interval intervals2[] = {{1, 4}, {1, 5}};
    
    int n2 = sizeof(intervals2) / sizeof(intervals2[0]);

    mergeIntervals(intervals2, n2);
    
    return 0;
}
{[1, 4], [1, 5]}
{[1, 5]}

الأسلوب الأمثل لدمج الفترات

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

مثال

الفترات الأصلية: {[5 ، 8] ، [3 ، 6] ، [15 ، 25] ، [10 ، 14] ، [9 ، 13]}
بعد الفرز: {[[3 ، 6] ، [5 ، 8] ، [9 ، 13] ، [10 ، 14] ، [15 ، 25]}
في هذا المثال ، من الواضح أن فترات التقاطع جاءت متجاورة بعد الفرز ، لذلك نحتاج فقط إلى مقارنة الفترات المتجاورة.
يتم دمج [3 ، 6] و [5 ، 8] في [3 ، 8]
يتم دمج [9 ، 14] و [10 ، 14] في [9 ، 14]
الناتج : {[3، 8]، [9، 14]، [15، 25]}

كود مزيف

ل [] -> الحد الأدنى (نقطة البداية) لجميع الفواصل الزمنية
r [] -> الحد الأعلى (نقطة النهاية) لجميع الفواصل الزمنية
ن -> العدد الإجمالي للفترات الزمنية

Sort l and r as described.
for (int i = 0; i < n - 1; i++) {
  // Compare i and (i + 1)th intervals
  if ((l[i] >= l[i + 1] && l[i] <= r[i + 1]) || (r[i] >= l[i + 1] && r[i] <= r[i + 1])) {
    // Merge intervals
    l[i + 1] = min(l[i], l[i + 1])
    r[i + 1] = max(r[i], r[i + 1])
    // Remove the previous interval
    l[i] = -infinity
    r[i] = -infinity
  }
}
// Print the merged intervals
for (int i = 0; i < n; i++) {
  if (!(l[i] == -infinity && r[i] == -infinity)) {
    // Print only non removed intervals
    print(l[i] + " " + r[i])
  }
}

تعقيد الوقت = O (ن * سجل (ن)) حيث n هو عدد الفترات المعطاة. نستخدم وظيفة الفرز للفرز والتي تستغرق وقتًا طويلاً.

كود جافا

public class MergingIntervals {
    // Function to merge the intervals and print merged intervals
    private static void mergeIntervals(Interval intervals[]) {
        // Sort the intervals array
        Arrays.sort(intervals, Interval.comp);

        // Traverse the sorted array
        for (int i = 0; i < intervals.length - 1; i++) {
            // Compare i and (i + 1)th intervals
            if ((intervals[i].l >= intervals[i + 1].l && intervals[i].l <= intervals[i + 1].r)
                    || (intervals[i].r >= intervals[i + 1].l && intervals[i].r <= intervals[i + 1].r)) {
                // Merge intervals
                intervals[i + 1].l = Math.min(intervals[i].l, intervals[i + 1].l);
                intervals[i + 1].r = Math.max(intervals[i].r, intervals[i + 1].r);
                // Remove previous interval
                intervals[i].l = Integer.MIN_VALUE;
                intervals[i].r = Integer.MIN_VALUE;
            } else {
                // Do not merge
            }
        }

        // Print the merged intervals
        for (int i = 0; i < intervals.length; i++) {
            if (!(intervals[i].l == Integer.MIN_VALUE && intervals[i].r == Integer.MIN_VALUE)) {
                System.out.println(intervals[i].l + " " + intervals[i].r);
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        Interval intervals[] = new Interval[4];
        intervals[0] = new Interval(1, 3);
        intervals[1] = new Interval(2, 6);
        intervals[2] = new Interval(8, 10);
        intervals[3] = new Interval(15, 18);

        mergeIntervals(intervals);

        // Example 2
        Interval intervals2[] = new Interval[2];
        intervals2[0] = new Interval(1, 4);
        intervals2[1] = new Interval(1, 5);

        mergeIntervals(intervals2);
    }

    // Class representing an interval
    static class Interval {
        int l;      // Staring point
        int r;      // Ending point

        public Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }

        // Comparator to sort the intervals
        public static final Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                int l1 = o1.l;
                int l2 = o2.l;
                int r1 = o1.r;
                int r2 = o2.r;

                if (l1 == l2) {
                    return Integer.compare(r1, r2);
                }

                return Integer.compare(l1, l2);
            }
        };
    }
}

كود C ++

#include <bits/stdc++.h>
using namespace std;

// Structure representing an interval
struct Interval {
    int l, r;
};

// Comparator for sorting intervals
bool compareInterval(Interval i1, Interval i2) {
    if (i1.l == i2.l) {
        return (i1.r < i2.r);
    }
    return (i1.l < i2.l);
}

// Function to merge the intervals and print merged intervals
void mergeIntervals(Interval intervals[], int n) {
    // Sort the intervals array
    sort(intervals, intervals + n, compareInterval);
    
    // Traverse the sorted array
    for (int i = 0; i < n - 1; i++) {
        // Compare i and (i + 1)th intervals
        if ((intervals[i].l >= intervals[i + 1].l && intervals[i].l <= intervals[i + 1].r) || (intervals[i].r >= intervals[i + 1].l && intervals[i].r <= intervals[i + 1].r)) {
            // Merge intervals
            intervals[i + 1].l = std::min(intervals[i].l, intervals[i + 1].l);
            intervals[i + 1].r = std::max(intervals[i].r, intervals[i + 1].r);
            // Remove previous interval
            intervals[i].l = INT_MIN;
            intervals[i].r = INT_MIN;
        } else {
            // Do not merge
        }
    }
    
    // Print the merged intervals
    for (int i = 0; i < n; i++) {
        if (!(intervals[i].l == INT_MIN && intervals[i].r == INT_MIN)) {
            cout<<intervals[i].l<<" "<<intervals[i].r<<endl;
        }
    }
}

int main() {
    // Example 1
    Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    
    int n1 = sizeof(intervals) / sizeof(intervals[0]);

    mergeIntervals(intervals, n1);

    // Example 2
    Interval intervals2[] = {{1, 4}, {1, 5}};
    
    int n2 = sizeof(intervals2) / sizeof(intervals2[0]);

    mergeIntervals(intervals2, n2);
    
    return 0;
}
{[5, 8], [3, 6], [15, 25], [10, 14], [9, 13]}
{[3, 8], [9, 14], [15, 25]}

مراجع