Check if any interval completely overlaps the other
An interval is represented as a combination of start time and end time. Given a set of intervals, we need to write a program to check if any interval completely overlaps the other.
Examples:
Input: arr[] = {{1, 3}, {1, 7}, {4, 8}, {2, 5}}
Output: true
Explanation: The intervals {1, 3} completely overlaps in {1, 7}.Input: arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}}
Output: false
Explanation: No pair of intervals overlap.
Naive Approach
A Simple Solution is to consider every pair of intervals and check if the pair overlaps or not.
Follow the given steps to solve the problem:
- Iterate through each interval i, and for each interval i, loop through all the intervals j.
- For two intervals i and j,
- Check if the start time of interval i is less than or equal to the start time of interval j and the end time of interval i is greater than or equal to the end time of interval j.
- Check if the start time of interval j is less than or equal to the start time of interval i and the end time of interval j is greater than or equal to the start time of interval i.
- If any of above two condition is true, print indices of intervals i and j.
- If no intervals completely overlap each other, print “No overlapping intervals found”.
Below is the implementation of the approach:
// C++ code for the approach
#include <iostream>
#include <vector>
using namespace std;
// An interval has start time and end time
struct Interval {
int start, end;
};
// Function to check if any interval
// completely overlaps the other
bool isOverlap(const Interval& i1, const Interval& i2) {
if (i1.start <= i2.start && i1.end >= i2.end) {
return true;
}
if (i2.start <= i1.start && i2.end >= i1.end) {
return true;
}
return false;
}
// Function to check if any interval in the given set
// overlaps completely with another interval
bool hasCompleteOverlap(const vector<Interval>& intervals) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isOverlap(intervals[i], intervals[j])) {
return true;
}
}
}
return false;
}
// Driver's Code
int main() {
// 1st example
vector<Interval> intervals1 = { { 1, 3 }, { 1, 7 }, { 4, 8 },
{ 2, 5 } };
if (hasCompleteOverlap(intervals1)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
// 2nd example
vector<Interval> intervals2 = { { 1, 3 }, { 7, 9 }, { 4, 6 },
{ 10, 13 } };
if (hasCompleteOverlap(intervals2)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
import java.util.ArrayList;
// An interval has start time and end time
class Interval {
int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public class Main {
// Function to check if any interval
// completely overlaps the other
static boolean isOverlap(Interval i1, Interval i2) {
if (i1.start <= i2.start && i1.end >= i2.end) {
return true;
}
if (i2.start <= i1.start && i2.end >= i1.end) {
return true;
}
return false;
}
// Function to check if any interval in the given set
// overlaps completely with another interval
static boolean hasCompleteOverlap(ArrayList<Interval> intervals) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isOverlap(intervals.get(i), intervals.get(j))) {
return true;
}
}
}
return false;
}
// Driver's Code
public static void main(String[] args) {
// 1st example
ArrayList<Interval> intervals1 = new ArrayList<>();
intervals1.add(new Interval(1, 3));
intervals1.add(new Interval(1, 7));
intervals1.add(new Interval(4, 8));
intervals1.add(new Interval(2, 5));
if (hasCompleteOverlap(intervals1)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
// 2nd example
ArrayList<Interval> intervals2 = new ArrayList<>();
intervals2.add(new Interval(1, 3));
intervals2.add(new Interval(7, 9));
intervals2.add(new Interval(4, 6));
intervals2.add(new Interval(10, 13));
if (hasCompleteOverlap(intervals2)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
# Python code for the above approach
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
# Function to check if any interval completely overlaps the other
def is_overlap(i1, i2):
if i1.start <= i2.start and i1.end >= i2.end:
return True
if i2.start <= i1.start and i2.end >= i1.end:
return True
return False
# Function to check if any interval in the given set overlaps completely with another interval
def has_complete_overlap(intervals):
n = len(intervals)
for i in range(n):
for j in range(i + 1, n):
if is_overlap(intervals[i], intervals[j]):
return True
return False
# Driver's Code
if __name__ == "__main__":
# 1st example
intervals1 = [
Interval(1, 3),
Interval(1, 7),
Interval(4, 8),
Interval(2, 5)
]
if has_complete_overlap(intervals1):
print("Yes")
else:
print("No")
# 2nd example
intervals2 = [
Interval(1, 3),
Interval(7, 9),
Interval(4, 6),
Interval(10, 13)
]
if has_complete_overlap(intervals2):
print("Yes")
else:
print("No")
#This code is contributed by aeroabrar_31
using System;
using System.Collections.Generic;
// An interval has start time and end time
public class Interval {
public int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public class GFG {
// Function to check if any interval
// completely overlaps the other
static bool isOverlap(Interval i1, Interval i2) {
if (i1.start <= i2.start && i1.end >= i2.end) {
return true;
}
if (i2.start <= i1.start && i2.end >= i1.end) {
return true;
}
return false;
}
// Function to check if any interval in the given set
// overlaps completely with another interval
static bool hasCompleteOverlap(List<Interval> intervals) {
int n = intervals.Count;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isOverlap(intervals[i], intervals[j])) {
return true;
}
}
}
return false;
}
// Driver's Code
static void Main(string[] args) {
// 1st example
List<Interval> intervals1 = new List<Interval>();
intervals1.Add(new Interval(1, 3));
intervals1.Add(new Interval(1, 7));
intervals1.Add(new Interval(4, 8));
intervals1.Add(new Interval(2, 5));
if (hasCompleteOverlap(intervals1)) {
Console.WriteLine("Yes");
} else {
Console.WriteLine("No");
}
// 2nd example
List<Interval> intervals2 = new List<Interval>();
intervals2.Add(new Interval(1, 3));
intervals2.Add(new Interval(7, 9));
intervals2.Add(new Interval(4, 6));
intervals2.Add(new Interval(10, 13));
if (hasCompleteOverlap(intervals2)) {
Console.WriteLine("Yes");
} else {
Console.WriteLine("No");
}
}
}
class Interval {
constructor(start, end) {
this.start = start;
this.end = end;
}
}
function isOverlap(i1, i2) {
if ((i1.start <= i2.start && i1.end >= i2.end) || (i2.start <= i1.start && i2.end >= i1.end)) {
return true;
}
return false;
}
function hasCompleteOverlap(intervals) {
const n = intervals.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isOverlap(intervals[i], intervals[j])) {
return true;
}
}
}
return false;
}
// 1st example
const intervals1 = [
new Interval(1, 3),
new Interval(1, 7),
new Interval(4, 8),
new Interval(2, 5)
];
if (hasCompleteOverlap(intervals1)) {
console.log("Yes");
} else {
console.log("No");
}
// 2nd example
const intervals2 = [
new Interval(1, 3),
new Interval(7, 9),
new Interval(4, 6),
new Interval(10, 13)
];
if (hasCompleteOverlap(intervals2)) {
console.log("Yes");
} else {
console.log("No");
}
//This code is contributed by aeroabrar_31
Output
Yes No
Time Complexity: O(n*n) as two nested for loops are executed. Here, n is size of the input array.
Auxiliary Space: O(1) as no extra space has been taken.
Check if any interval completely overlaps the other using Sorting:
A better solution is to use Sorting. The idea is to sort all intervals in increasing order of start time and then in the sorted array, if the end time of an interval is not more than the end time of the previous interval, then there is a complete overlap.
Follow the given steps to solve the problem:
- Sort the intervals in increasing order of start time.
- Interate through each interval:
- If the end time of an interval is not more than the end time of the previous interval, it means these two intervals overlap. Then Print the indices of the intervals.
- If no intervals completely overlap each other, print “No overlapping intervals found”.
Given below is an implementation of the above approach:
// A C++ program to check if any two intervals
// completely overlap
#include <bits/stdc++.h>
using namespace std;
// An interval has start time and end time
struct Interval {
int start;
int end;
};
// Compares two intervals according to their starting
// time. This is needed for sorting the intervals
// using library function std::sort().
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start) ? true : false;
}
// Function to check if any two intervals
// completely overlap
bool isOverlap(Interval arr[], int n)
{
// Sort intervals in increasing order of
// start time
sort(arr, arr + n - 1, compareInterval);
// In the sorted array, if end time of an
// interval is not more than that of
// end of previous interval, then there
// is an overlap
for (int i = 1; i < n; i++)
if (arr[i].end <= arr[i - 1].end)
return true;
// If we reach here, then no overlap
return false;
}
// Driver code
int main()
{
// 1st example
Interval arr1[] = { { 1, 3 }, { 1, 7 }, { 4, 8 },
{ 2, 5 } };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
if (isOverlap(arr1, n1))
cout << "Yes\n";
else
cout << "No\n";
// 2nd example
Interval arr2[] = { { 1, 3 }, { 7, 9 }, { 4, 6 },
{ 10, 13 } };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
if (isOverlap(arr2, n2))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
/*package whatever //do not write package name here */
import java.util.*;
class GFG {
// An interval has start time and end time
// Function to check if any two intervals
// completely overlap
static boolean isOverlap(int arr[][], int n)
{
// Sort intervals in increasing order of
// start time
Arrays.sort(arr, (i1,i2) -> i1[0]-i2[0]);
// In the sorted array, if end time of an
// interval is not more than that of
// end of previous interval, then there
// is an overlap
for (int i = 1; i < n; i++)
if (arr[i][1] <= arr[i - 1][1])
return true;
// If we reach here, then no overlap
return false;
}
public static void main (String[] args)
{
// 1st example
int arr1[][] = { { 1, 3 }, { 1, 7 }, { 4, 8 }, { 2, 5 } };
int n1 = arr1.length;
if (isOverlap(arr1, n1))
System.out.println("Yes");
else
System.out.println("No");
// 2nd example
int arr2[][] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } };
int n2 = arr2.length;
if (isOverlap(arr2, n2))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by aadityaburujwale.
# A Python program to check if any two intervals
# completely overlap
# Compares two intervals according to their starting
# time.
# Function to check if any two intervals
# completely overlap
def isOverlap(arr, n):
# Sort intervals in increasing order of
# start time
arr.sort()
# In the sorted array, if end time of an
# interval is not more than that of
# end of previous interval, then there
# is an overlap
for i in range(1, n):
if (arr[i][1] <= arr[i - 1][1]):
return True
# If we reach here, then no overlap
return False
# Driver code
# 1st example
arr1 = [[1, 3], [1, 7], [4, 8 ], [2, 5]]
n1 = len(arr1)
if (isOverlap(arr1, n1)):
print("Yes")
else:
print("No")
# 2nd example
arr2 = [[1, 3], [7, 9], [4, 6], [10, 13]]
n2 = len(arr2)
if (isOverlap(arr2, n2)):
print("Yes")
else:
print("No")
# This code is contributed by hardikkushwaha.
using System;
using System.Collections.Generic;
class GFG {
// An interval has start time and end time
class Interval {
public int start;
public int end;
public Interval(int start, int end)
{
this.start=start;
this.end=end;
}
};
// Compares two intervals according to their starting
// time. This is needed for sorting the intervals
// using library function std::sort().
/*bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start) ? true : false;
}*/
// Function to check if any two intervals
// completely overlap
static int isOverlap(Interval[] arr, int n)
{
// Sort intervals in increasing order of
// start time
//Array.Sort<int>(arr, new Comparison<int>(
//(i1, i2) => i2.CompareTo(i1)));
Array.Sort(arr, (i1, i2) => i1.start.CompareTo(i2.start));
// In the sorted array, if end time of an
// interval is not more than that of
// end of previous interval, then there
// is an overlap
for (int i = 1; i < n; i++)
if (arr[i].end <= arr[i - 1].end)
return 1;
// If we reach here, then no overlap
return 0;
}
// Driver code
public static void Main()
{
// 1st example
Interval[] arr1 = { new Interval(1, 3 ), new Interval(1, 7), new Interval(4, 8 ), new Interval(2, 5 ) };
int n1 = arr1.Length;
if (isOverlap(arr1, n1)==1)
Console.Write("Yes\n");
else
Console.Write("No\n");
// 2nd example
Interval[] arr2 = { new Interval(1, 3 ), new Interval(7, 9), new Interval(4, 6 ), new Interval(10, 13 ) };
int n2 = arr2.Length;
if (isOverlap(arr2, n2)==1)
Console.Write("Yes\n");
else
Console.Write("No\n");
}
}
// This code is contributed by poojaagarwal2.
<script>
// A JavaScript program to check if any two intervals
// completely overlap
// An interval has start time and end time
// Compares two intervals according to their starting
// time. This is needed for sorting the intervals
// using library function std::sort().
const compareInterval = (i1, i2) => i1.start - i2.start;
// Function to check if any two intervals
// completely overlap
const isOverlap = (arr, n) => {
// Sort intervals in increasing order of
// start time
arr.sort(compareInterval);
// In the sorted array, if end time of an
// interval is not more than that of
// end of previous interval, then there
// is an overlap
for (let i = 1; i < n; i++)
if (arr[i].end <= arr[i - 1].end)
return true;
// If we reach here, then no overlap
return false;
}
// Driver code
// 1st example
let arr1 = [
{ start: 1, end: 3 },
{ start: 1, end: 7 },
{ start: 4, end: 8 },
{ start: 2, end: 5 }
];
let n1 = arr1.length;
if (isOverlap(arr1, n1))
document.write("Yes<br/>");
else
document.write("No<br/>");
// 2nd example
let arr2 = [
{ start: 1, end: 3 },
{ start: 7, end: 9 },
{ start: 4, end: 6 },
{ start: 10, end: 13 }
];
let n2 = arr2.length;
if (isOverlap(arr2, n2))
document.write("Yes<br/>");
else
document.write("No<br/>");
// This code is contributed by rakeshsahni
</script>
Output
Yes No
Time Complexity: O(n log n).
Auxiliary Space: O(1)