K overlapping segment

Concepts Used:

Stack.

Difficulty Level:

Medium.

Problem Statement :

Arnab is hosting a party but he has only k seats. Guest have come at different times and leave at different times.Help Arnab find if there is k guest present at any time. If there is k or more people print Yes so that he may bring more chairs else print No.
Guest leave the chair after leaving time ,so at leaving time the chair is occupied.
Solve it using stack.

See original problem statement here

Example:

Input:
1
3 3 
1 2
2 3
2 4

Output:
yes

Explanation:
At time 1: only guest 1 is present.
At time 2: guests 1,2 and 3 are present .
At time 3: guest 2 and 3 are present.

Solving Approach :

  1. The idea is to attend online coding classes to make a vector of pair 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).
  2. Now, sort the vector then traverse the vector and if the current element is a starting point then push it in a stack and if it is an ending point then pop an element from the stack.
  3. If at any instance of time, the size of the stack is greater than or equal K then print Yes else print No in the end.

Solutions:

    #include <bits/stdc++.h> 
    using namespace std; 
    bool 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); 
    } 
    bool kOverlap(vector<pair<int, int> > pairs, int k) 
    { 
    vector<pair<int, int> > vec; 
    for (int i = 0; i < pairs.size(); i++) { 

        vec.push_back(make_pair( pairs[i].first, -1 )); 
        vec.push_back(make_pair( pairs[i].second, +1 )); 
    } 
    sort(vec.begin(), vec.end()); 
    stack<pair<int, int> > st; 
    for (int i = 0; i < vec.size(); i++) { 
        pair<int, int> cur = vec[i]; 
        if (cur.second == -1) { 
            st.push(cur); 
        } 
        else { 
            st.pop(); 
        } 
        if (st.size() >= k) { 
            return true; 
        } 
    } 
    return false; 
    } 
     int main()
    {  
    int t;
    cin>>t;
    while(t--)
    {
    int n,k;
    cin>>n>>k;
    vector<pair<int, int> > pairs; 
    int x,y;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        pairs.push_back(make_pair(x,y));
    }
    if(kOverlap(pairs,k))
    cout<<"Yes"<<endl;
    else
    {
        cout<<"No"<<endl;
    }
    } 
    return 0;
    }
    import java.util.*;

    class solution{ 

    public static class Pair{
        int first;
        int second;
        Pair(int first,int second){
            first=this.first;
            second=this.second;
        }
    }

    static boolean sortby(Pair p1,Pair p2) 
    { 
    if (p1.first != p2.first) 
        return p1.first < p2.first; 
    return (p1.second < p2.second); 
    } 
    static boolean kOverlap(ArrayList<Pair> pairs, int k) 
    { 
    ArrayList<Pair> vec=new ArrayList<Pair>();
    for (int i = 0; i < pairs.size(); i++) { 

        vec.add(new Pair(pairs.get(i).first, -1 )); 
        vec.add(new Pair(pairs.get(i).second, +1 )); 
    } 
    Collections.sort(vec, new Comparator<Pair>() {
    @Override
    public int compare(final Pair p1,final Pair p2) {
        return p1.first-p2.first;
    }
    });
    Stack<Pair> st=new Stack<Pair>(); 
    for (int i = 0; i < vec.size(); i++) { 
        Pair cur = vec.get(i); 
        if (cur.second == -1) { 
            st.push(cur); 
        } 
        else { 
            st.pop(); 
        } 
        if (st.size() >= k) { 
            return true; 
        } 
    } 
    return false; 
    } 
     public static void main (String[] args) {
     Scanner sc=new Scanner(System.in);

    int t=sc.nextInt();
    while(t-->0)
    {
    int n,k;
    n=sc.nextInt();k=sc.nextInt();
    ArrayList<Pair> pairs=new ArrayList<Pair>();
    int x,y;
    for(int i=0;i<n;i++)
    {
        x=sc.nextInt();
        y=sc.nextInt();
        pairs.add(new Pair(x,y));
    }
    if(kOverlap(pairs,k)==true)
    System.out.println("Yes");
    else
    {
        System.out.println("No");
    }
    } 
    }
     }

Previous post Max Rectangle
Next post Count Components

Leave a Reply

Your email address will not be published. Required fields are marked *