KGSS - Maximum Sum

EXPLANATION:

we are going to use segment tree for this because the time complexity of update and query in segment tree ,both are O(logn). And Time Complexity for tree construction is O(n).

NOTE:Since we have to find sum of two number in an interval , we will store two numbers in every nodes : 

1st=highest number in that interval 

2nd=second highest number in that interval.

consider an example : 

          ARR[5]={1,2,3,4,5};

segment tree for this will look like this:  

QUERY:

suppose if our query range is 3,4 :it means (3-1,4-1)=(2,3) we have to find two number in range ARR[2] to ARR[3] such that there sum is  maximum.(position of both number should be different).

So we will start recursive call to query:

since 0,4 is  not within the interval 2,3 we will calculate mid position and call query again.

mid = (start+end)/2;

mid = (0+4)/2;    //   mid = 2

now we will check whether query interval is within left child or right child.

Note:start and end indicates the range of ARR.

if(r is less than or equal to mid == true)

   return query(1(left child index),0(start),2(end),2(left),3(end))

otherwise if(l is greater than mid)

   return query((2(right child index),3(start),4(end),2(left),3(end))

since both case are not true then:it means that range lie in two different  nodes. so we will find the query in both left child and right child . than we will combine the result left(3,MIN_INT) and right (4,MIN_INT). so our result will be (4,3);

So ans is 4+3=7.

NOTE:MIN_INT is the minimun int value possible which  used  for leaf nodes .

UPDATE:

For update we will use recursive call to update with  index of tree , the interval and position and  newvalue .

what we have to do is we have to update all the ranges which include that position of ARR.

first we will update the leaf node by recursive till start=end.

than all the inner node having that position in range will be updated.

if(position is less than equal to mid)

          then we will update left child.

else

          we will update right child.

NOTE FOR MAKING TREE NODES:

for resultant.first we are taking maximum of firstmax of both child BUT for resultant.second we are taking minimum of max because maximum is already selected for  first so we will go minimum one i.e the second highest.

CODE:

#include <iostream>

#include <bits/stdc++.h>

#include <math.h>

using namespace std;

typedef struct segment

{

int firstmax;

int secondmax;

}NODE;

NODE TREE[3*100005];

int ARR[100010],m=0;

/*int max(int a,int b)

{

return a>b?a:b;

}

int min(int a,int b)

{

return a<b?a:b;

}*/

void build_seg_tree(int index,int start,int end)

{

/*to store the leaf node with firstmax element with the arr value 

and secondmax element with least int value so that during comparison 

both node value will be choosen*/

if(start==end)

{

TREE[index].firstmax=ARR[start];//start or end anything can be used

TREE[index].secondmax=INT_MIN;//minimum value of int (datatype) that can be possible

}

else

{

int mid=(start+end)/2;

build_seg_tree(2*index+1,start,mid);

build_seg_tree(2*index+2,mid+1,end);

TREE[index].firstmax=max(TREE[2*index+1].firstmax,TREE[2*index+2].firstmax);

TREE[index].secondmax=min(max(TREE[2*index+1].firstmax,TREE[2*index+2].secondmax),max(TREE[2*index+1].secondmax,TREE[2*index+2].firstmax));

/*if(2*index+2>m)

m=2*index+2;*/

}

}

NODE query(int index,int start,int end,int l,int r)

{

NODE result;

result.firstmax=-1;

result.secondmax=-1;

if(l>end||r<start)

return result;

if(end<=r&&l<=start)

return TREE[index];

int mid=(start+end)/2;

if(r<=mid)

return query(2*index+1,start,mid,l,r);

if(l>mid)

return query(2*index+2,mid+1,end,l,r);

NODE left=query(2*index+1,start,mid,l,r);

NODE right=query(2*index+2,mid+1,end,l,r);

result.firstmax=max(left.firstmax,right.firstmax);

result.secondmax=min(max(left.firstmax,right.secondmax),max(left.secondmax,right.firstmax));

return result;

}

void update(int index,int start,int end,int pos,int newitem)

{

if(start==end)

{

TREE[index].firstmax=newitem;

}

else

{

int mid=(start+end)/2;

if(pos<=mid)

update(2*index+1,start,mid,pos,newitem);

else

update(2*index+2,mid+1,end,pos,newitem);

TREE[index].firstmax=max(TREE[2*index+1].firstmax,TREE[2*index+2].firstmax);

TREE[index].secondmax=min(max(TREE[2*index+1].firstmax,TREE[2*index+2].secondmax),max(TREE[2*index+1].secondmax,TREE[2*index+2].firstmax));

}

}

int main()

{

int n,q,i,a,b,j;

char ch;

cin>>n;

for(i=0;i<n;i++)

cin>>ARR[i];

build_seg_tree(0,0,n-1);

/*for(j=0;j<=m;j++)

cout<<"first "<<TREE[j].firstmax<<" and second "<<TREE[j].secondmax<<endl;*/

cin>>q;

for(i=0;i<q;i++)

{

cin>>ch>>a>>b;

if(ch=='Q')

{

NODE ans=query(0,0,n-1,a-1,b-1);

cout<<ans.firstmax+ans.secondmax<<endl;

}

else

update(0,0,n-1,a-1,b);

/*for(j=0;j<=m;j++)

cout<<"first "<<TREE[j].firstmax<<" and second "<<TREE[j].secondmax<<endl;*/

}

return 0;

}

BUSYMAN - I AM VERY BUSY

EXPLANATION:

you are given set of 'n' activities with their time slot  and between that time slot only that activity can be done. 
So basically what we can do is :
 1. first we will sort all the activities according to their ending time in ascending order.
 2.than we will start selecting activity according to their to ending time and starting time.

So after sorting we will declare some 'prevend' variable and initialised to -1 or any other negative value , this variable will store the ending time of previously selected activity.
And declare a variable 'ans' which is initialised  to 0 , this will store the number of activities that can be done.

if(the starting time of next activity is greater than or equal to previous ending time )
  then 
   {      
             prevend is updated with ending time of selected activity and
             increment the number of activity that can be done by 1
   }

NOTE:sorting of array or vector of pair first compare the first element if they are same than second  element is considered.

SOLUTION:

USING VECTOR AND PAIR (STL)[C++]

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<pair<int,int> > SCHEDULE;
vector<pair<int,int> > ::iterator itr;
int t,n,i,a,b,ans,prevend;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
SCHEDULE.push_back(make_pair(b,a));
}
sort(SCHEDULE.begin(),SCHEDULE.end());
/*for(itr=SCHEDULE.begin();itr!=SCHEDULE.end();itr++)
{
cout<<itr->first<<" "<<itr->second<<endl;
}*/
ans=0;
prevend=-1;
for(itr=SCHEDULE.begin();itr!=SCHEDULE.end();itr++)
if(itr->second>=prevend)
{
ans++;
prevend=itr->first;
}
cout<<ans<<endl;
SCHEDULE.clear();
}
return 0;
}

USING ARRAY AND PAIR (STL)[C++]

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,n,i,a,b,ans,prevend;
cin>>t;
while(t--)
{
cin>>n;
pair<int,int> SCHEDULE[n];
for(i=0;i<n;i++)
{
cin>>a>>b;
SCHEDULE[i]=make_pair(b,a);
}
sort(SCHEDULE,SCHEDULE+n);
ans=0;
prevend=-1;
for(i=0;i<n;i++)
if(SCHEDULE[i].second>=prevend)
{
ans++;
prevend=SCHEDULE[i].first;
}
cout<<ans<<endl;
}
return 0;
}