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.
Mündəricat
Nümunələr
Input
{[1, 3], [2, 6], [8, 10], [15, 18]}
Buraxılış
{[1, 6], [8, 10], [15, 18]}
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]}
