Given N ranges [L, R] and an integer K, the task is to check if there are any K ranges that overlap at any point.
Examples:
Input: ranges[][] = {{1, 3}, {2, 4}, {3, 4}, {7, 10}}, K = 3
Output: Yes
3 is a common point among the
ranges {1, 3}, {2, 4} and {3, 4}.Input: ranges[][] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}}, K = 2
Output: No
Approach: The idea is to make a vector of pairs and store the starting point for every range as pair in this vector as (starting point, -1) and the ending point as (ending point, 1). Now, sort the vector then traverse the vector and if the current element is a starting point then push it into a stack and if it is an ending point then pop an element from the stack. If at any instance of time, the size of the stack is greater than or equal to K then print Yes else print No in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Comparator to sort the vector of pairsbool sortby(const pair<int, int>& a, const pair<int, int>& b){ if (a.first != b.first) return a.first < b.first; return (a.second < b.second);}// Function that returns true if any k// segments overlap at any pointbool kOverlap(vector<pair<int, int> > pairs, int k){ // Vector to store the starting point // and the ending point vector<pair<int, int> > vec; for (int i = 0; i < pairs.size(); i++) { // Starting points are marked by -1 // and ending points by +1 vec.push_back({ pairs[i].first, -1 }); vec.push_back({ pairs[i].second, +1 }); } // Sort the vector by first element sort(vec.begin(), vec.end()); // Stack to store the overlaps stack<pair<int, int> > st; for (int i = 0; i < vec.size(); i++) { // Get the current element pair<int, int> cur = vec[i]; // If it is the starting point if (cur.second == -1) { // Push it in the stack st.push(cur); } // It is the ending point else { // Pop an element from stack st.pop(); } // If more than k ranges overlap if (st.size() >= k) { return true; } } return false;}// Driver codeint main(){ vector<pair<int, int> > pairs; pairs.push_back(make_pair(1, 3)); pairs.push_back(make_pair(2, 4)); pairs.push_back(make_pair(3, 5)); pairs.push_back(make_pair(7, 10)); int n = pairs.size(), k = 3; if (kOverlap(pairs, k)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.Stack;class GFG{static class Pair { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; }}// Function that returns true if any k// segments overlap at any pointstatic boolean kOverlap(ArrayList<Pair> pairs, int k){ // Vector to store the starting point // and the ending point ArrayList<Pair> vec = new ArrayList<>(); for(int i = 0; i < pairs.size(); i++) { // Starting points are marked by -1 // and ending points by +1 vec.add(new Pair(pairs.get(i).first, -1)); vec.add(new Pair(pairs.get(i).second, +1)); } // Sort the vector by first element Collections.sort(vec, new Comparator<Pair>() { // Comparator to sort the vector of pairs public int compare(Pair a, Pair b) { if (a.first != b.first) return a.first - b.first; return (a.second - b.second); } }); // Stack to store the overlaps Stack<Pair> st = new Stack<>(); for(int i = 0; i < vec.size(); i++) { // Get the current element Pair cur = vec.get(i); // If it is the starting point if (cur.second == -1) { // Push it in the stack st.push(cur); } // It is the ending point else { // Pop an element from stack st.pop(); } // If more than k ranges overlap if (st.size() >= k) { return true; } } return false;}// Driver codepublic static void main(String[] args){ ArrayList<Pair> pairs = new ArrayList<>(); pairs.add(new Pair(1, 3)); pairs.add(new Pair(2, 4)); pairs.add(new Pair(3, 5)); pairs.add(new Pair(7, 10)); int n = pairs.size(), k = 3; if (kOverlap(pairs, k)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation of the approach# Function that returns true if any k# segments overlap at any pointdef kOverlap(pairs: list, k): # Vector to store the starting point # and the ending point vec = list() for i in range(len(pairs)): # Starting points are marked by -1 # and ending points by +1 vec.append((pairs[0], -1)) vec.append((pairs[1], 1)) # Sort the vector by first element vec.sort(key = lambda a: a[0]) # Stack to store the overlaps st = list() for i in range(len(vec)): # Get the current element cur = vec[i] # If it is the starting point if cur[1] == -1: # Push it in the stack st.append(cur) # It is the ending point else: # Pop an element from stack st.pop() # If more than k ranges overlap if len(st) >= k: return True return False# Driver Codeif __name__ == "__main__": pairs = list() pairs.append((1, 3)) pairs.append((2, 4)) pairs.append((3, 5)) pairs.append((7, 10)) n = len(pairs) k = 3 if kOverlap(pairs, k): print("Yes") else: print("No")# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approachusing System;using System.Collections;using System.Collections.Generic;class GFG{// Function that returns true if any k// segments overlap at any pointstatic bool kOverlap(List<Tuple<int,int>> pairs, int k){ // Vector to store the starting point // and the ending point List<Tuple<int,int>> vec = new List<Tuple<int,int>>(); for(int i = 0; i < pairs.Count; i++) { // Starting points are marked by -1 // and ending points by +1 vec.Add(new Tuple<int,int>(pairs[i].Item1,-1)); vec.Add(new Tuple<int,int>(pairs[i].Item2,1)); } vec.Sort(); // Stack to store the overlaps Stack st = new Stack(); for(int i = 0; i < vec.Count; i++) { // Get the current element Tuple<int,int> cur = vec[i]; // If it is the starting point if (cur.Item2 == -1) { // Push it in the stack st.Push(cur); } // It is the ending point else { // Pop an element from stack st.Pop(); } // If more than k ranges overlap if (st.Count >= k) { return true; } } return false;}// Driver codepublic static void Main(params string[] args){ List<Tuple<int,int>> pairs = new List<Tuple<int,int>>(); pairs.Add(new Tuple<int,int>(1, 3)); pairs.Add(new Tuple<int,int>(2, 4)); pairs.Add(new Tuple<int,int>(3, 5)); pairs.Add(new Tuple<int,int>(7, 10)); int n = pairs.Count, k = 3; if (kOverlap(pairs, k)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by rutvik_56/ |
Javascript
<script>// JavaScript implementation of the approach// Function that returns true if any k// segments overlap at any pointfunction kOverlap(pairs, k){ // Vector to store the starting point // and the ending point var vec = []; for (var i = 0; i < pairs.length; i++) { // Starting points are marked by -1 // and ending points by +1 vec.push([pairs[i][0], -1 ]); vec.push([pairs[i][1], +1 ]); } // Sort the vector by first element vec.sort((a,b)=>{ if(a[0]!=b[0]) return a[0]-b[0] return a[1]-b[1] }); // Stack to store the overlaps var st = []; for (var i = 0; i < vec.length; i++) { // Get the current element var cur = vec[i]; // If it is the starting point if (cur[1] == -1) { // Push it in the stack st.push(cur); } // It is the ending point else { // Pop an element from stack st.pop(); } // If more than k ranges overlap if (st.length >= k) { return true; } } return false;}// Driver codevar pairs = [];pairs.push([1, 3]);pairs.push([2, 4]);pairs.push([3, 5]);pairs.push([7, 10]);var n = pairs.length, k = 3;if (kOverlap(pairs, k)) document.write( "Yes");else document.write( "No");</script> |
Output
Yes
Time Complexity: O(N*logN), as we sort an array of size N. Where N is the number of pairs in the array.
Auxiliary Space: O(N), as we are using extra space for the array vec and stack st. Where N is the number of pairs in the array.
Approach(Using brute force):
- The function kOverlap takes a vector of pairs representing N ranges, and an integer K as input.
- The function first sorts the input vector of ranges in ascending order of the start point of each range.
- It then iterates through the sorted ranges, keeping track of the maximum endpoint of the K ranges seen so far and the number of overlapping ranges.
- If the current range overlaps with the K ranges seen so far, the function updates the maximum endpoint and increments the overlap count.
- If the current range doesn’t overlap with the K ranges seen so far, the function checks if K overlapping ranges have been found so far. If yes, it returns true; otherwise, it resets the overlap count and maximum endpoint for the next set of ranges.
- The function returns false if no K overlapping ranges are found in the entire vector of ranges.
C++
#include <bits/stdc++.h>using namespace std;// Function that returns true if any k// segments overlap at any pointbool kOverlap(vector<pair<int, int> > pairs, int k){ // Sort the vector by start point of each // range sort(pairs.begin(), pairs.end()); // Keep track of the maximum endpoint of= // k ranges seen so far int maxEndpoint = pairs[0].second; int overlapCount = 1; for (int i = 1; i < pairs.size(); i++) { // If the current range overlaps with // the k ranges seen so far if (pairs[i].first <= maxEndpoint) { overlapCount++; maxEndpoint = max(maxEndpoint, pairs[i].second); } // If the current range doesn't overlap // with the k ranges seen so far else { // If k overlapping ranges /// have been found if (overlapCount >= k) { return true; } // Reset the counters for the // next set of ranges overlapCount = 1; maxEndpoint = pairs[i].second; } } // Check if the last set of ranges // overlap k times or more if (overlapCount >= k) { return true; } // No k overlapping ranges found return false;}// Driver codeint main(){ vector<pair<int, int> > pairs = { { 1, 3 }, { 2, 4 }, { 3, 5 }, { 7, 10 } }; int k = 3; // Function call if (kOverlap(pairs, k)) cout << "Yes"; else cout << "No"; return 0;} |
Java
import java.util.Arrays;public class Main { public static void main(String[] args) { int[][] pairs = { {1, 3}, {2, 4}, {3, 5}, {7, 10} }; int k = 3; if (kOverlap(pairs, k)) { System.out.println("Yes"); } else { System.out.println("No"); } } public static boolean kOverlap(int[][] pairs, int k) { // Sort the array of pairs by the start point of each range Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0])); // Keep track of the maximum endpoint of k ranges seen so far int maxEndpoint = pairs[0][1]; int overlapCount = 1; for (int i = 1; i < pairs.length; i++) { // If the current range overlaps with the k ranges seen so far if (pairs[i][0] <= maxEndpoint) { overlapCount++; maxEndpoint = Math.max(maxEndpoint, pairs[i][1]); } else { // If k overlapping ranges have been found if (overlapCount >= k) { return true; } // Reset the counters for the next set of ranges overlapCount = 1; maxEndpoint = pairs[i][1]; } } // Check if the last set of ranges overlap k times or more return overlapCount >= k; }} |
Python3
def k_overlap(pairs, k): pairs.sort(key=lambda x: x[0]) # Sort the pairs by the start point max_endpoint = pairs[0][1] overlap_count = 1 for i in range(1, len(pairs)): if pairs[i][0] <= max_endpoint: # If the current range overlaps overlap_count += 1 max_endpoint = max(max_endpoint, pairs[i][1]) else: # If the current range doesn't overlap if overlap_count >= k: # If k overlapping ranges have been found return True overlap_count = 1 max_endpoint = pairs[i][1] if overlap_count >= k: # Check if the last set of ranges overlap k times or more return True return False # No k overlapping ranges found# Driver codepairs = [(1, 3), (2, 4), (3, 5), (7, 10)]k = 3# Function callif k_overlap(pairs, k): print("Yes")else: print("No") |
C#
using System;using System.Collections.Generic;class GFG{ // Function that returns true if any k segments overlap at any point static bool KOverlap(List<Tuple<int, int>> pairs, int k) { // Sort the list of tuples by start point of each range pairs.Sort((a, b) => a.Item1.CompareTo(b.Item1)); // Keep track of the maximum endpoint of k ranges seen so far int maxEndpoint = pairs[0].Item2; int overlapCount = 1; for (int i = 1; i < pairs.Count; i++) { // If the current range overlaps with the k ranges seen so far if (pairs[i].Item1 <= maxEndpoint) { overlapCount++; maxEndpoint = Math.Max(maxEndpoint, pairs[i].Item2); } // If the current range doesn't overlap with the k ranges seen so far else { // If k overlapping ranges have been found if (overlapCount >= k) { return true; } // Reset the counters for the next set of ranges overlapCount = 1; maxEndpoint = pairs[i].Item2; } } // Check if the last set of ranges overlap k times or more if (overlapCount >= k) { return true; } // No k overlapping ranges found return false; } // Driver code static void Main() { List<Tuple<int, int>> pairs = new List<Tuple<int, int>>() { new Tuple<int, int>(1, 3), new Tuple<int, int>(2, 4), new Tuple<int, int>(3, 5), new Tuple<int, int>(7, 10) }; int k = 3; // Function call if (KOverlap(pairs, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }} |
Javascript
// Function that returns true if any k segments overlap at any pointfunction kOverlap(pairs, k) { // Sort the array of pairs by the start point of each range pairs.sort((a, b) => a[0] - b[0]); // Keep track of the maximum endpoint of k ranges seen so far let maxEndpoint = pairs[0][1]; let overlapCount = 1; for (let i = 1; i < pairs.length; i++) { // If the current range overlaps with the k ranges seen so far if (pairs[i][0] <= maxEndpoint) { overlapCount++; maxEndpoint = Math.max(maxEndpoint, pairs[i][1]); } else { // If k overlapping ranges have been found if (overlapCount >= k) { return true; } // Reset the counters for the next set of ranges overlapCount = 1; maxEndpoint = pairs[i][1]; } } // Check if the last set of ranges overlap k times or more if (overlapCount >= k) { return true; } // No k overlapping ranges found return false;}// Driver codeconst pairs = [ [1, 3], [2, 4], [3, 5], [7, 10]];const k = 3;// Function callif (kOverlap(pairs, k)) { console.log("Yes");} else { console.log("No");} |
Output
Yes
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
