Posted on by Kalkicode
Code Array

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:

  1. [7, 21]
  2. [2, 20]
  3. [9, 28]
  4. [4, 21]
  5. [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
  1. Initialize 'a' and 'b' to the start and end points of the first interval (intervals[0][0] and intervals[0][1]).
  2. Iterate through the remaining intervals (from 1 to n-1).
  3. 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].
  4. After the iteration, check if 'a' and 'b' are present in every interval.
  5. If 'a' and 'b' exist in all intervals, output the intersection interval [a, b], else output -1.

Algorithm Explanation

  1. Start by initializing 'a' and 'b' to the start and end points of the first interval (intervals[0][0] and intervals[0][1]).
  2. 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].
  3. 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.

Comment

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





Categories
Relative Post