Aralıqları birləşdirir

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Cisco eBay Facebook Goldman Sachs google IXL microsoft Kahin Palantir Texnologiyaları PayPal Boşalmaq kvadrat cuqquldamaq Über VMware Walmart Laboratoriyaları Yahoo Yandex
Geyim çeşidləyiciBaxılıb 27

Aralıqları birləşdirmək məsələsində [l, r] formasının bir sıra intervalı verdik, üst-üstə düşən aralıqları birləşdirin.

Nümunələr

Input
{[1, 3], [2, 6], [8, 10], [15, 18]}
Buraxılış
{[1, 6], [8, 10], [15, 18]}

Aralıqları birləşdirirPin

Input
{[1, 4], [1, 5]}
Buraxılış
{[1, 5]}

Aralıqları birləşdirmək üçün sadəlövh yanaşma

Üçün sadəlövh yanaşma birləşmə intervallar sadəcə hər intervalın qalan bütün intervallarla müqayisə edilməsidir. Bəzi kəsişmə nöqtəsi varsa, ikinci hissəni çıxarın və birincisinə birləşdirin.

Saxta Kod

L [] bütün aralıqların alt həddini (başlanğıc nöqtəsini) və r [] bütün aralıqların yuxarı həddini (bitmə nöqtəsini) təmsil etsin.

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]);
  }
}

Zaman Mürəkkəbliyi = O (n ^ 2) burada n verilən intervalların sayıdır. Burada N * N vaxt aparan hər bir aralığın cütlüyünü yoxlayırıq.

JAVA Kodu

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 ++ kodu

#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]}

Aralıqları birləşdirmək üçün optimal yanaşma

Birləşmə aralığına optimal yanaşma, iki fasilənin eyni başlanğıc nöqtəsinə sahib olduğu təqdirdə, aralıqları başlanğıc nöqtəsinə (alt sərhəd) görə artan sıraya görə sıralamaqdır, cür bitmə nöqtəsinə görə artan sırada. Bu, bəzi ümumi nöqtələrə sahib ola bilən fasilələrin bir-birinin ardınca baş verməsini təmin edəcəkdir. Çeşidlədikdən sonra bitişik aralıqları müqayisə edin və sadəlövh yanaşmada olduğu kimi birləşdirin.

misal

Orijinal fasilələr: {[5, 8], [3, 6], [15, 25], [10, 14], [9, 13]}
Çeşidlədikdən sonra: {[[3, 6], [5, 8], [9, 13], [10, 14], [15, 25]}
Bu nümunədə kəsişən aralıqların çeşidləndikdən sonra bir-birinin yanına gəldiyi aydındır, buna görə yalnız bitişik aralıqları müqayisə etməliyik.
[3, 6] və [5, 8] [3, 8] ilə birləşir
[9, 14] və [10, 14] [9, 14] ilə birləşir
Buraxılış : {[3, 8], [9, 14], [15, 25]}

Saxta Kod

l [] -> Bütün fasilələrin alt həddi (Başlanğıc nöqtəsi)
r [] -> Bütün fasilələrin yuxarı həddi (Bitmə nöqtəsi)
n -> Aralıqların ümumi sayı

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])
  }
}

Zaman Mürəkkəbliyi = O (n * log (n)) burada n verilən intervalların sayıdır. Sıralama üçün çox vaxt alan sort funksiyasından istifadə edirik.

JAVA Kodu

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 ++ kodu

#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]}

References

Translate »