Problem solving using STL (Standard Template Library) for Competitive Programming














































Problem solving using STL (Standard Template Library) for Competitive Programming



Here are some problems which can easily be solved with the use of STL functions. 
If you want to learn and explore STL then you must visit my previous article before this one.

1) Reception Arrangement 

There is only one beauty parlor in the town of Malhesari. The receptionist at the beauty parlor is flooded with appointment requests because the "Teeja" festival is round the corner and everyone wants to look good on it. She needs your help. The problem is they don't have chairs in reception. They are ordering chairs from FellaKart. They don't want to order more than required. You have to tell the minimum number of chairs required such that none of the customers has to stand.

Input Format :
First line contains the number of customers that will come. Second line contains N space-separated integers which represent the arrival timings of the customer. Third line contains N space-separated integers which represent the departure timings of the customer. Arrival and departure timings are given in 24-hour clock.
Constraints:
1<= N <= 100
Arrival and departure timings lie in the range [0000 to 2359]
Time Limit: 1 second
Output Format :
You have to print the minimum number of chairs required such that no customer has to wait standing.
Sample Test Cases:

Sample Input 1 :

5
900 1000 1100 1030 1600
1900 1300 1130 1130 1800

Sample Output 1:

4

Explanation:

4 because at 1100 hours, we will have maximum number of customers at the shop, throughout the day. And that maximum number is 4.
Solution in C++ :-

// Program to find minimum number of chairs // required in the reception
#include<bits/stdc++.h> using namespace std; int chair(int arr[], int dep[], int n) { // Sort arrival and departure arrays using STL function sort(arr, arr+n); sort(dep, dep+n); // chair_needed indicates number of chairs // needed at a time int chair_needed = 1, result = 1; int i = 1, j = 0; // Similar to merge in merge sort to process // all events in sorted order while (i < n && j < n) { // If next event in sorted order is arrival, // increment count of chairs needed if (arr[i] <= dep[j]) { chair_needed++; i++; // Update result if needed if (chair_needed > result) result = plat_needed; } // Else decrement count of chairs needed else { chair_needed--; j++; } } return result; } // Driver program to test methods of graph class int main() { int n,i; cin>>n; int arr[n]; int dep[n]; for(i=0;i<n;i++) cin>>arr[i]; for(i=0;i<n;i++) cin>>dep[i]; cout <<chair(arr, dep, n); return 0; }



2) Different Names

In Little Flowers Public School, there are many students with same first names. You are given a task to find the students with same names. You will be given a string comprising of all the names of students and you have to tell the name and count of those students having same. If all the names are unique, print -1 instead.

Note: We don't have to mention names whose frequency is 1.

Input Format:
The only line of input will have a string %u2018str%u2019 with space separated first names of students.
Output Format:
Print the names of students along with their count if they are repeating. If no name is repeating, print -1
Constraints:
1 <= |str| <= 10^5
Time Limit: 1 second
Sample Input 1:
Abhishek harshit Ayush harshit Ayush Iti Deepak Ayush Iti
Sample Output 1:
harshit 2
Ayush 3
Iti 2
Sample Input 2:
Abhishek Harshit Ayush Iti
Sample Output:
-1
Solution in C++ :-

//Program to find the no. of times
//a name is arriving in the string
#include<bits/stdc++.h> using namespace std; int main (){ string s; int count=0; // Taking input string from user
getline(cin,s); // Taking an empty string temp
string temp="";
// Defining map unordered_map<string,int> m; for(int i=0;i<s.length();i++){ if(s[i]==' '){ // Iterating the names into map
m[temp]++; temp=""; }else{ temp=temp+s[i]; } if(i==s.length()-1){ m[temp]++; } } // Declaring the iterator to map
unordered_map<string,int>::iterator it; for(it=m.begin();it!=m.end();it++){ if(it->second>=2){
// Printing the repeated names along with their frequency cout<<it->first<<" "<<it->second<<endl; count++; } } if(count==0) cout<<-1; return 0; }

More Articles of Shivam Gupta:

Name Views Likes
Programming in C++ using boost.asio 729 1
Understanding Time and Space Complexity for Competitive Programming 1414 1
Standard Template Library (STL) of C++ || STL - Data Structures for Competitive Programming 498 1
Synchronous Chatting Application using C++ boost::asio 1199 1
C++ program to print bottom view of a binary tree 1064 1
How to do Competitive Programming? 330 1
Recursion problem solving in C++ 5970 1
Problem solving using STL (Standard Template Library) for Competitive Programming 2268 1
Understanding Pointers for Data Structures 360 1
How to apply Recursion 434 1

Comments