3rd sort both arrarys according to last coach position, the make a min priority queue and insert the first element of array(train with least position of last coach), if starting position of next train is less top of priority queue the we need new platform else update priority queue.
Very difficult to explain but still I will try to give you some points
1)
Only column matters therefore make an array which contains only systems and therefore res[i] will contain all system having column i.
2)
How efficiently can you calculate pairwise distance between all 2 columns.
Hint ->
suppose we have columns 1 and 2
Column 1 will contain these 2,3,4 (row no) this denote there is a system at v[2][1],v[3][1]......
Column 2 will contain 1,5,7,8
Now to calculate distance between column 1 and column 2
Pair wise b/w column 1 and 2 i.e 2-1,2-5,2-7,2-8,3-1,3-5,3-7,3-8,4-1,4-5,4-7,4-8
int temp= abs(col[j]*cnt[i]- col[i]cnt[j]) + abs(jcnt[j]cnt[i] - icnt[i]*cnt[j]); here the first term is for |c1-c2| and other is for |r1-r2|
elements In column 1 i.e distance between 2-3 ,2-4,3-4 sum[1][0] stores this distance
elements In column 2 i.e 2-5,2-7,2-8,5-7,5-8 sum[2][0] stores this distance
3)
Suppose we have columns 1,2,3,4 and k=2
then we have to calculate distance between
1-2,1-3,2-3 and between elements in the same column
or 2-3,2-4,3-4 and between elements in the same column
Sum[i][j] will store sum of distance of elements in column i from elements in (column i to column i+j)
2nd problem
void solve(){
vector<string>v{".&.",".&.","&.&"};
int n=v.size();
int m=v[0].size();
int k=3;
vector<int>col(m+1,0);
vector<int>cnt(m+1,0);
vector<vector<int>>res(m+1);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(v[i][j]=='&'){
col[j+1]+=i+1; //it stores the sum of row value of all the system at column j
res[j+1].push_back(i+1);
cnt[j+1]++; //count
}
}
}
int sum[m+1][m+1]; //sum[i][j] tells the pair wise sum when we are considering all elements in column[i] and all elements between column i and column i+j
memset(sum,0,sizeof(sum));
for(int i=1;i<=m;i++){
int x=cnt[i];
int t=0;
for(int j=0;j<res[i].size();j++){
t+=res[i][j];
sum[i][0]+=abs((col[i]-t)-(x-1)*res[i][j]);
x--;
}
}
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
int d=j-i;
int temp= abs(col[j]*cnt[i]- col[i]*cnt[j]) + abs(j*cnt[j]*cnt[i] - i*cnt[i]*cnt[j]);
sum[i][d]=temp+sum[i][d-1];
}
}
//suppose we are calculating all columns at dist p1 from column i then for the next column we need to calculate at distance p1-1
int mx=0;
for(int i=1;i<=m;i++){
int ans=0;
int p1=k;
for(int j=i;j<=m;j++){
int u=m-j; //if max distance from column i is less than p1
ans+= sum[j][min(u,p1)];
p1--;
if(p1<0)break;
}
mx=max(mx,ans);
}
cout<<mx;
}
1st, just sort v[d] , d = 1 to 15, and answer the query like v[d][k].
2nd can't solve. (Any idea how to solve in N^2 ? ).
3rd sort both engine and rear positions, the trick was if engine[i] > rear[i] , swap(engine[i] , rear[i]) . Now the problem reduces to meeting rooms 2. Sort both
initiliaze i = 0 , j = 0, if engine[i] <= rear[i] ++cnt , ++i, else --cnt , ++j. Ans = max(ans, cnt) , return ans.