Find intersection of all intervals
In this article, we will explore how to find the intersection of all given intervals. An interval is represented by a pair of integers [a, b], where 'a' is the start point, and 'b' is the end point of the interval. The goal is to determine the common part that exists in all intervals and find the minimum and maximum points that are present in all of them.
Problem Statement
Given 'n' intervals represented as a 2D array 'intervals', we need to find the intersection interval [a, b], such that every interval in the array contains both 'a' and 'b'. If no such common interval exists, we will output -1.
Example
Consider the following intervals:
- [7, 21]
- [2, 20]
- [9, 28]
- [4, 21]
- [6, 25]
We can visually represent the intervals on a number line as follows:
2 6 9 20 21 25 28
|---------|---------|---------|---------|---------|---------|
Interval: [2, 20] [4, 21] [6, 25] [7, 21] [9, 28]
The intersection interval [a, b] that exists in all given intervals is [9, 20]. So, the output of the program should be "9 20".
Pseudocode
// Function to find the intersection of all intervals
// intervals: 2D array representing the intervals [a, b]
// n: number of intervals
function intersectionIntervals(intervals[][], n):
// Initialize 'a' and 'b' to the start and end points of the first interval
a = intervals[0][0]
b = intervals[0][1]
// Find the minimum and maximum of all given intervals
for i = 1 to n-1:
if intervals[i][0] > a:
a = intervals[i][0]
if intervals[i][1] < b:
b = intervals[i][1]
// Check if 'a' and 'b' exist in each interval
for i = 0 to n-1:
if !(a >= intervals[i][0] && a <= intervals[i][1]) or
!(b >= intervals[i][0] && b <= intervals[i][1]):
// When 'a' or 'b' does not exist in an interval
output "None (-1)"
return
// Output the intersection interval
output a, b
- Initialize 'a' and 'b' to the start and end points of the first interval (intervals[0][0] and intervals[0][1]).
- Iterate through the remaining intervals (from 1 to n-1).
- For each interval, update 'a' to the maximum of 'a' and intervals[i][0], and 'b' to the minimum of 'b' and intervals[i][1].
- After the iteration, check if 'a' and 'b' are present in every interval.
- If 'a' and 'b' exist in all intervals, output the intersection interval [a, b], else output -1.
Algorithm Explanation
- Start by initializing 'a' and 'b' to the start and end points of the first interval (intervals[0][0] and intervals[0][1]).
- For each remaining interval (from 1 to n-1): a. Update 'a' to the maximum of the current 'a' and intervals[i][0]. b. Update 'b' to the minimum of the current 'b' and intervals[i][1].
- After the iteration, check if 'a' and 'b' are present in every interval: a. Iterate through all intervals and check if 'a' lies between intervals[i][0] and intervals[i][1], and similarly for 'b'. b. If 'a' and 'b' do not exist in any interval, output -1, as there is no common intersection. c. Otherwise, output the intersection interval [a, b].
Code Solution
Here given code implementation process.
// C Program
// Find intersection of all intervals
#include <stdio.h>
void intersectionIntervals(int intervals[][2], int n)
{
int a = intervals[0][0];
int b = intervals[0][1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for (int i = 1; i < n; ++i)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
}
// Check a and b are exist in each interval or not
for (int i = 0; i < n; ++i)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
printf("\n None (-1) \n");
return;
}
}
// Display resultant interval
printf("\n %d %d \n", a, b);
}
int main()
{
int intervals[][2] = {
{
7 , 21
},
{
2 , 20
},
{
9 , 28
},
{
4 , 21
},
{
6 , 25
}
};;
// Get the size
int n = sizeof(intervals) / sizeof(intervals[0]);
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
intersectionIntervals(intervals, n);
return 0;
}
Output
9 20
/*
Java Program
Find intersection of all intervals
*/
public class Intervals
{
public void intersectionIntervals(int intervals[][], int n)
{
int a = intervals[0][0];
int b = intervals[0][1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for (int i = 1; i < n; ++i)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
}
// Check a and b are exist in each interval or not
for (int i = 0; i < n; ++i)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
System.out.print("\n None (-1) \n");
return;
}
}
// Display resultant interval
System.out.print("\n " + a + " " + b + " \n");
}
public static void main(String[] args)
{
Intervals task = new Intervals();
int[][] intervals = {
{
7 , 21
},
{
2 , 20
},
{
9 , 28
},
{
4 , 21
},
{
6 , 25
}
};
// Get the size
int n = intervals.length;
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
}
Output
9 20
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Find intersection of all intervals
*/
class Intervals
{
public: void intersectionIntervals(int intervals[][2], int n)
{
int a = intervals[0][0];
int b = intervals[0][1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for (int i = 1; i < n; ++i)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
}
// Check a and b are exist in each interval or not
for (int i = 0; i < n; ++i)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
cout << "\n None (-1) \n";
return;
}
}
// Display resultant interval
cout << "\n " << a << " " << b << " \n";
}
};
int main()
{
Intervals *task = new Intervals();
int intervals[][2] = {
{
7 , 21
} , {
2 , 20
} , {
9 , 28
} , {
4 , 21
} , {
6 , 25
}
};
// Get the size
int n = sizeof(intervals) / sizeof(intervals[0]);
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task->intersectionIntervals(intervals, n);
return 0;
}
Output
9 20
// Include namespace system
using System;
/*
Csharp Program
Find intersection of all intervals
*/
public class Intervals
{
public void intersectionIntervals(int[,] intervals, int n)
{
int a = intervals[0,0];
int b = intervals[0,1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for (int i = 1; i < n; ++i)
{
if (a < intervals[i,0])
{
a = intervals[i,0];
}
if (b > intervals[i,1])
{
b = intervals[i,1];
}
}
// Check a and b are exist in each interval or not
for (int i = 0; i < n; ++i)
{
if (!(a >= intervals[i,0] && a <= intervals[i,1]) ||
!(b >= intervals[i,0] && b <= intervals[i,1]))
{
// When interval not exist
Console.Write("\n None (-1) \n");
return;
}
}
// Display resultant interval
Console.Write("\n " + a + " " + b + " \n");
}
public static void Main(String[] args)
{
Intervals task = new Intervals();
int[,] intervals = {
{
7 , 21
},
{
2 , 20
},
{
9 , 28
},
{
4 , 21
},
{
6 , 25
}
};
// Get the size
int n = intervals.GetLength(0);
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
}
Output
9 20
package main
import "fmt"
/*
Go Program
Find intersection of all intervals
*/
func intersectionIntervals(intervals[][] int, n int) {
var a int = intervals[0][0]
var b int = intervals[0][1]
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for i := 1 ; i < n ; i++ {
if a < intervals[i][0] {
a = intervals[i][0]
}
if b > intervals[i][1] {
b = intervals[i][1]
}
}
// Check a and b are exist in each interval or not
for i := 0 ; i < n ; i++ {
if !(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]) {
// When interval not exist
fmt.Print("\n None (-1) \n")
return
}
}
// Display resultant interval
fmt.Print("\n ", a, " ", b, " \n")
}
func main() {
var intervals = [][] int {
{ 7, 21 },
{ 2, 20 },
{ 9, 28 } ,
{ 4, 21 } ,
{ 6, 25 } }
// Get the size
var n int = len(intervals)
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
intersectionIntervals(intervals, n)
}
Output
9 20
<?php
/*
Php Program
Find intersection of all intervals
*/
class Intervals
{
public function intersectionIntervals($intervals, $n)
{
$a = $intervals[0][0];
$b = $intervals[0][1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for ($i = 1; $i < $n; ++$i)
{
if ($a < $intervals[$i][0])
{
$a = $intervals[$i][0];
}
if ($b > $intervals[$i][1])
{
$b = $intervals[$i][1];
}
}
// Check a and b are exist in each interval or not
for ($i = 0; $i < $n; ++$i)
{
if (!($a >= $intervals[$i][0] && $a <= $intervals[$i][1]) ||
!($b >= $intervals[$i][0] && $b <= $intervals[$i][1]))
{
// When interval not exist
echo("\n None (-1) \n");
return;
}
}
// Display resultant interval
echo("\n ".$a." ".$b." \n");
}
}
function main()
{
$task = new Intervals();
$intervals = array(
array(7, 21),
array(2, 20),
array(9, 28),
array(4, 21),
array(6, 25)
);
// Get the size
$n = count($intervals);
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
$task->intersectionIntervals($intervals, $n);
}
main();
Output
9 20
/*
Node JS Program
Find intersection of all intervals
*/
class Intervals
{
intersectionIntervals(intervals, n)
{
var a = intervals[0][0];
var b = intervals[0][1];
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
for (var i = 1; i < n; ++i)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
}
// Check a and b are exist in each interval or not
for (var i = 0; i < n; ++i)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
process.stdout.write("\n None (-1) \n");
return;
}
}
// Display resultant interval
process.stdout.write("\n " + a + " " + b + " \n");
}
}
function main()
{
var task = new Intervals();
var intervals = [
[7, 21],
[2, 20],
[9, 28],
[4, 21],
[6, 25]
];
// Get the size
var n = intervals.length;
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
main();
Output
9 20
# Python 3 Program
# Find intersection of all intervals
class Intervals :
def intersectionIntervals(self, intervals, n) :
a = intervals[0][0]
b = intervals[0][1]
i = 1
# Find min and max of given intervals.
# Find maximum of first slot
# And minimum element in second slot.
while (i < n) :
if (a < intervals[i][0]) :
a = intervals[i][0]
if (b > intervals[i][1]) :
b = intervals[i][1]
i += 1
i = 0
# Check a and b are exist in each interval or not
while (i < n) :
if (not(a >= intervals[i][0] and a <= intervals[i][1]) or
not(b >= intervals[i][0] and b <= intervals[i][1])) :
# When interval not exist
print("\n None (-1) ")
return
i += 1
# Display resultant interval
print("\n ", a ," ", b ," ")
def main() :
task = Intervals()
intervals = [
[7, 21],
[2, 20],
[9, 28],
[4, 21],
[6, 25]
]
# Get the size
n = len(intervals)
# Test A
# arr = [0, 1, 0,1]
# --------------------------
# Intervals
# a b
# [ 7, 21 ]
# [ 2, 20 ]
# [ 9, 28 ]
# [ 4, 21 ]
# [ 6, 25 ]
# ↆ ↆ
# 9 20 Step 1
# Max Min [Find min max of given slot]
# ---------------
# Step 2 :
# Check that each interval pair contain pair of
# (a,b) or not.
# (a = 9, b=20)
# Intervals
# [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
# [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
# [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
# [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
# [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
# ------------------------------------------
# When all yes
# Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n)
if __name__ == "__main__": main()
Output
9 20
# Ruby Program
# Find intersection of all intervals
class Intervals
def intersectionIntervals(intervals, n)
a = intervals[0][0]
b = intervals[0][1]
i = 1
# Find min and max of given intervals.
# Find maximum of first slot
# And minimum element in second slot.
while (i < n)
if (a < intervals[i][0])
a = intervals[i][0]
end
if (b > intervals[i][1])
b = intervals[i][1]
end
i += 1
end
i = 0
# Check a and b are exist in each interval or not
while (i < n)
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
# When interval not exist
print("\n None (-1) \n")
return
end
i += 1
end
# Display resultant interval
print("\n ", a ," ", b ," \n")
end
end
def main()
task = Intervals.new()
intervals = [
[7, 21],
[2, 20],
[9, 28],
[4, 21],
[6, 25]
]
# Get the size
n = intervals.length
# Test A
# arr = [0, 1, 0,1]
# --------------------------
# Intervals
# a b
# [ 7, 21 ]
# [ 2, 20 ]
# [ 9, 28 ]
# [ 4, 21 ]
# [ 6, 25 ]
# ↆ ↆ
# 9 20 Step 1
# Max Min [Find min max of given slot]
# ---------------
# Step 2 :
# Check that each interval pair contain pair of
# (a,b) or not.
# (a = 9, b=20)
# Intervals
# [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
# [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
# [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
# [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
# [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
# ------------------------------------------
# When all yes
# Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n)
end
main()
Output
9 20
/*
Scala Program
Find intersection of all intervals
*/
class Intervals()
{
def intersectionIntervals(intervals: Array[Array[Int]],
n: Int): Unit = {
var a: Int = intervals(0)(0);
var b: Int = intervals(0)(1);
var i: Int = 1;
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
while (i < n)
{
if (a < intervals(i)(0))
{
a = intervals(i)(0);
}
if (b > intervals(i)(1))
{
b = intervals(i)(1);
}
i += 1;
}
i = 0;
// Check a and b are exist in each interval or not
while (i < n)
{
if (!(a >= intervals(i)(0) && a <= intervals(i)(1)) ||
!(b >= intervals(i)(0) && b <= intervals(i)(1)))
{
// When interval not exist
print("\n None (-1) \n");
return;
}
i += 1;
}
// Display resultant interval
print("\n " + a + " " + b + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Intervals = new Intervals();
var intervals: Array[Array[Int]] = Array(
Array(7, 21),
Array(2, 20),
Array(9, 28),
Array(4, 21),
Array(6, 25)
);
// Get the size
var n: Int = intervals.length;
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
}
Output
9 20
import Foundation;
/*
Swift 4 Program
Find intersection of all intervals
*/
class Intervals
{
func intersectionIntervals(_ intervals: [
[Int]
], _ n: Int)
{
var a: Int = intervals[0][0];
var b: Int = intervals[0][1];
var i: Int = 1;
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
while (i < n)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
i += 1;
}
i = 0;
// Check a and b are exist in each interval or not
while (i < n)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
print("\n None (-1) ");
return;
}
i += 1;
}
// Display resultant interval
print("\n ", a ," ", b ," ");
}
}
func main()
{
let task: Intervals = Intervals();
let intervals: [
[Int]
] = [
[7, 21],
[2, 20],
[9, 28],
[4, 21],
[6, 25]
];
// Get the size
let n: Int = intervals.count;
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
main();
Output
9 20
/*
Kotlin Program
Find intersection of all intervals
*/
class Intervals
{
fun intersectionIntervals(
intervals: Array < Array < Int >> ,
n: Int): Unit
{
var a: Int = intervals[0][0];
var b: Int = intervals[0][1];
var i: Int = 1;
// Find min and max of given intervals.
// Find maximum of first slot
// And minimum element in second slot.
while (i < n)
{
if (a < intervals[i][0])
{
a = intervals[i][0];
}
if (b > intervals[i][1])
{
b = intervals[i][1];
}
i += 1;
}
i = 0;
// Check a and b are exist in each interval or not
while (i < n)
{
if (!(a >= intervals[i][0] && a <= intervals[i][1]) ||
!(b >= intervals[i][0] && b <= intervals[i][1]))
{
// When interval not exist
print("\n None (-1) \n");
return;
}
i += 1;
}
// Display resultant interval
print("\n " + a + " " + b + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Intervals = Intervals();
val intervals: Array < Array < Int >> = arrayOf(
arrayOf(7, 21),
arrayOf(2, 20),
arrayOf(9, 28),
arrayOf(4, 21),
arrayOf(6, 25)
);
// Get the size
val n: Int = intervals.count();
// Test A
// arr = [0, 1, 0,1]
// --------------------------
// Intervals
//
// a b
// [ 7, 21 ]
// [ 2, 20 ]
// [ 9, 28 ]
// [ 4, 21 ]
// [ 6, 25 ]
// ↆ ↆ
// 9 20 Step 1
// Max Min [Find min max of given slot]
// ---------------
// Step 2 :
// Check that each interval pair contain pair of
// (a,b) or not.
//
// (a = 9, b=20)
// Intervals
// [ 7, 21 ] Yes [7...21 contains 9 and 20 ]
// [ 2, 20 ] Yes [2...20 contains 9 and 20 ]
// [ 9, 28 ] Yes [9...28 contains 9 and 20 ]
// [ 4, 21 ] Yes [4...21 contains 9 and 20 ]
// [ 6, 25 ] Yes [6...25 contains 9 and 20 ]
// ------------------------------------------
// When all yes
// Then result (9,20) otherwise -1
task.intersectionIntervals(intervals, n);
}
Output
9 20
Resultant Output Explanation
In the given example, after running the program, it will calculate 'a' as 9 and 'b' as 20. The program then checks if [9, 20] is present in all intervals and confirms that it is. Hence, the output of the program will be "9 20", representing the intersection interval of all the given intervals.
Time Complexity
The time complexity of this algorithm is O(n) because we only iterate through the 'intervals' array once to find the minimum and maximum values. Therefore, the overall time complexity is linear, where 'n' represents the number of intervals in the input array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment