HackerEarth Rooms problem solution

YASH PAL, 31 July 202416 February 2026

In this HackerEarth Rooms problem solution, Harsh is thinking of starting his own business.He has decided to start with the hotel business. He has been given a list which contains the arrival time and the duration of stay of each guest at his hotel.

He can give 1 room to only 1 guest.Since he does not want to disappoint his guests he wants to find the minimum number of rooms he need to build so that he could accomodate all the guests. Help him in finding this answer.

HackerEarth Rooms problem solution

HackerEarth Rooms problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define total 5000005
#define M 1000000000001
#define NIL 0
#define MAXN 100001
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;
int a[100005];
vector<pair<int,int> >v;
priority_queue<int,vector<int>,greater<int> >p;
int main(){
    int i,j,t,n,s,d;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++){
            scanf("%d",&d);
            v.pb(mp(a[i],a[i]+d));
        }
        sort(all(v));
        int cnt=1;
        p.push(v[0].second);
        for(i=1;i<v.size();i++){
            d=v[i].first;
            j=p.top();
            if(d>=j){
                p.pop();
                p.push(v[i].second);
            }
            else{
                cnt++;
                p.push(v[i].second);
            }
        }
        printf("%dn",cnt);
        v.clear();
        p=priority_queue<int,vector<int>,greater<int> >();
    }
    return 0;
}

Second solution

import java.io.*;
import java.util.*;
public final class hotel_stay
{
    static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out=new PrintWriter(System.out);
    static Pair[] c;
    static Node[] tree;

    static void build(int node,int l,int r)
    {
        if(l>r)
        {
            return;
        }
        if(l==r)
        {
            tree[node]=new Node(l,c[l].r);
        }
        else
        {
            int mid=(l+r)>>1;
            build(node<<1,l,mid);
            build(node<<1|1,mid+1,r);
            if(tree[node<<1].val<tree[node<<1|1].val)
            {
                tree[node]=tree[node<<1];
            }
            else
            {
                tree[node]=tree[node<<1|1];
            }
        }
    }

    static Node getMin(int node,int s,int e,int l,int r)
    {
        if(s>e || l>e || r<s)
        {
            return new Node(-1,Long.MAX_VALUE);
        }
        if(l<=s && r>=e)
        {
            return tree[node];
        }
        else
        {
            int mid=(s+e)>>1;
            Node q1=getMin(node<<1,s,mid,l,r);
            Node q2=getMin(node<<1|1,mid+1,e,l,r);
            if(q1.val<q2.val)
            {
                return q1;
            }
            else
            {
                return q2;
            }
        }
    }

    static void update(int node,int s,int e,int l,int r,long val)
    {
        if(s>e || l>e || r<s)
        {
            return;
        }
        if(l<=s && r>=e)
        {
            if(tree[node].idx==l)
            {
                tree[node].val=val;
            }
        }
        else
        {
            int mid=(s+e)>>1;
            update(node<<1,s,mid,l,r,val);
            update(node<<1|1,mid+1,e,l,r,val);
            if(tree[node<<1].val<tree[node<<1|1].val)
            {
                tree[node]=tree[node<<1];
            }
            else
            {
                tree[node]=tree[node<<1|1];
            }
        }
    }

    public static void main(String args[]) throws Exception
    {
        int t=sc.nextInt();
        while(t>0)
        {
            int n=sc.nextInt(),max=1;
            long[] a=new long[n],b=new long[n];
            c=new Pair[n];
            tree=new Node[4*n];
            for(int i=0;i<n;i++)
            {
                a[i]=sc.nextLong();
            }
            for(int i=0;i<n;i++)
            {
                b[i]=sc.nextLong();
                c[i]=new Pair(a[i],a[i]+b[i]);
            }
            Arrays.sort(c);
            build(1,0,n-1);
            int ans=0;
            for(int i=0;i<n;i++)
            {
                Node min_node=getMin(1,0,n-1,0,i-1);
                //out.println(i+" "+min_node.val);
                if(min_node.val<=c[i].l)
                {
                    update(1,0,n-1,min_node.idx,min_node.idx,Long.MAX_VALUE);
                    continue;
                }
                else
                {
                    ans++;
                }
            }
            out.println(ans);
            t--;
        }
        out.close();
    }
}
class Pair implements Comparable<Pair>
{
    long l,r;
    public Pair(long l,long r)
    {
        this.l=l;
        this.r=r;
    }
    public int compareTo(Pair x)
    {
        return Long.compare(this.l,x.l);
    }
}
class Node
{
    int idx;
    long val;
    public Node(int idx,long val)
    {
        this.idx=idx;
        this.val=val;
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public String next() throws Exception {
        return nextToken().toString();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply