Last Updated on March 23, 2022 by Ria Pathak
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 :
- The idea is 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).
- 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.
- 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");
}
}
}
}
# your code goes here
def kOverlap(pairs, k):
vec = []
for i in range(len(pairs)):
vec.append([pairs[i][0], -1])
vec.append([pairs[i][1], 1])
vec.sort()
st = []
for i in range(len(vec)):
cur = vec[i]
if cur[1] == -1:
st.append(cur)
else:
st.pop()
if len(st) >= k:
return True
return False
for _ in range(int(input())):
n, k = map(int,input().split())
pairs = []
for i in range(n):
pairs.append(list(map(int,input().split())))
if kOverlap(pairs, k):
print("Yes")
else:
print("No")
[forminator_quiz id="1963"]
This article tried to discuss Stack. Hope this blog helps you understand and solve the problem. To practice more problems on Stack you can check out MYCODE | Competitive Programming.