# Daily Coding Challenge #5

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
People Whose List of Favorite Companies Is Not a Subset of Another List

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

Example 1:

Output: [0,1,4]
Explanation:
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].
Example 2:

Output: [0,1]
Example 3:

Output: [0,1,2,3]

Constraints:

1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
All strings in favoriteCompanies[i] are distinct.
All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
All strings consist of lowercase English letters only.
*/

class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
vector<int> ans;
// in order to use includes later on, sort the list first
for(auto &c:favoriteCompanies) sort(c.begin(),c.end());
// the favoriteCompanies length is small, traverse each possibilities
for(int i=0;i<favoriteCompanies.size();i++){
// reset found flag
bool found=false;
for(int j=0;j<favoriteCompanies.size();j++){
// skip if is found or the index is same
if(i==j ||found) continue;
// use std::includes() to check if favoriteCompanies[i] is a subset of favoriteCompanies[j] or not
found=includes(favoriteCompanies[j].begin(),favoriteCompanies[j].end(), favoriteCompanies[i].begin(), favoriteCompanies[i].end());
}
// if not, i is one of the answers
if(!found) ans.push_back(i);
}
return ans;
}
};
``````

``````/*
Rearrange Words in a Sentence

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.
Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.
Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.
Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

text begins with a capital letter and then contains lowercase letters and single space between words.
1 <= text.length <= 10^5
*/

class Solution {
public:
bool compare(pair<int,string> &s1,pair<int,string> &s2) {
// If they have the same size, order by original order
// else order by size
return s1.second.size()==s2.second.size()? s1.first<s2.first: s1.second.size()<s2.second.size();
}

string arrangeWords(string text) {
// First letter is in upper case.
// Convert it to lower case first.
text=tolower(text);
stringstream ss(text);
string word, ans="";
vector<pair<int,string>> v;
int i=0;
// put each word with original order to a pair
while(ss>>word){
v.push_back({i,word});
i++;
}
// sort with comparator
sort(v.begin(),v.begin()+i,[this](pair<int,string>& a, pair<int,string>& b){return compare(a,b);});

// build the result
for(int i=0;i<v.size();i++){
ans+=v[i].second;
if(i!=v.size()-1) ans+=" ";
}
// First letter needs to be in upper case.
ans=toupper(ans);
return ans;
}
};
``````

``````/*
Number of Students Doing Homework at a Given Time

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.
Example 2:

Input: startTime = , endTime = , queryTime = 4
Output: 1
Explanation: The only student was doing their homework at the queryTime.
Example 3:

Input: startTime = , endTime = , queryTime = 5
Output: 0
Example 4:

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0
Example 5:

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Constraints:

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000
*/

class Solution {
public:
int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
int ans=0;
for(int i=0;i<startTime.size();i++){
// just traverse each time to see if queryTime are between startTime and endTime incursively
if(queryTime>=startTime[i]&&queryTime<=endTime[i]) ans++;
}
return ans;
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

### Discussion   