Hello everyone, I have recently created a youtube channel where I try to upload the DSA content regularly. I have created a playlist where I explained the concept of binary search in detail and its applications to various problems

I have covered over 15 problems of various difficulty levels in Binary Search Algorithm

So make sure to check it out and give your feedback.

Youtube Channel: https://shorturl.at/bdIS5

Binary Search Playlist: https://rb.gy/wkeu6

This is my MlogN approach of Hotel Queries Problem problem using only segment tree

Problem statement:Given a sequence of n numbers h1,h2,h3...hn that represents the free rooms in each hotel and another sequence of length m i.e r1,r2,.., rm which represents the number of rooms each group requires, we can assign a hotel to a group if it has enough rooms for the group, hence the task is to assign the leftmost hotel to each group which has enough rooms for the entire group. Print the 1-based index of the hotel that is assigned to each group, if no hotel can be assigned then print 0.

Approach: The requirement of the question is that for each group of size say ri, we move from left to right iterating over the hotels and whenever we find the hotel having enough rooms (hj >= ri) for the group we can assign those rooms and update the available rooms as (hj -= ri). The brute-force way to do this is O(n^2) and it will give TLE.

Optimizing: 1.The observation is that we require the index of the leftmost hotels having enough rooms, so, therefore, we can maintain a max segment tree for the hotel's array which will give us the maximum number of rooms available in each range of hotels, Now the little modification is that we create the segment tree array (say tree) of user-defined data type struct{ value, index}, hence, for the vertex v, tree[v].value gives the maximum rooms in the range that the vertex v holds and tree[v].index is the corresponding hotel's array index of the same maximum value.

2.Now we can query for each group, say for the group ri we start at the root vertex (say v) and go down the tree ,we first check the left child whether the value here is greater than equals to ri, if yes then we move left otherwise the target hotel lies on the right side hence we move right.

3.When we reach our required vertex say (ver) corresponding to a single target hotel we update the value of this vertex here as tree[ver].value -= ri and return the index tree[ver].index.

4.Similarly, we update the parent vertex value and index for each child while backtracking.

5.The condition when there is no relevant hotel can be handled by comparing the max value of the segtree with the required group size in O(1)

#include <bits/stdc++.h>
using namespace std;

 
struct Vertex{
  int value;
  int index;
};
const int MAXN=200011;
Vertex tree[4*MAXN];
#define INF -1e9+7;
 
// This generates a segment tree which can give me
// the maximum element in a range as well as the index of that element.
 
void build(int a[], int v, int tl, int tr){
 
    if(tl==tr){
        tree[v].value=a[tl];
        tree[v].index=tl+1;
        return;
    }
    int mid = (tl+tr)/2;
    build(a,2*v,tl,mid);
    build(a,2*v+1,mid+1,tr);
    if(tree[2*v].value >= tree[2*v+1].value){
       tree[v]=tree[2*v];
    }
    else{
       tree[v]=tree[2*v+1];
    }
}
 
int query(int v, int tl, int tr, int num){
 
     if(tree[v].value < num)
        return 0;
   
    if(tl==tr){
 
        tree[v].value = tree[v].value - num;
        return tree[v].index;
    }
 
 
   int mid = (tl+tr)/2;
 
   if(tree[2*v].value >= num){
      int idx = query(2*v,tl,mid,num);
      if(tree[2*v].value >= tree[2*v+1].value){
        tree[v] = tree[2*v];
      }
      else{
        tree[v]=tree[2*v+1];
      }
      return idx;
   }
   else{
      int idx= query(2*v+1,mid+1,tr,num);
       if(tree[2*v].value >= tree[2*v+1].value){
         tree[v]=tree[2*v];
      }
      else{
       tree[v]=tree[2*v+1];
      }
 
      return idx;
   }
 
   
 
}

void solve(){
 
    int n,m;
    cin >> n >> m;
    int h[n],r[m];
    for(int i=0;i<n;i++)cin >> h[i];
    for(int i=0;i<m;i++)cin >> r[i];
    build(h,1,0,n-1);
 
    for(int i=0;i<m;i++)
    cout << query(1,0,n-1,r[i]) << " ";
 
}

Time Complexity: As for build it is O(n), for the query it is O(logn), the overall complexity becomes O(mlogn)

Note: This is my first or second blog here at cf so please forgive my mistakes :)