/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
class LogMessage{
public:
string sourceName;
string content;
LogMessage(string sourceName, string content) {
this->sourceName = sourceName;
this->content = content;
}
};
class Solution {
private:
bool check(unordered_map<string, vector<string>>&m, int mid, int maxSize) {
int trucateMessageCount = 0;
for(auto it = m.begin(); it!=m.end(); it++) {
if (it->second.size() > mid) {
trucateMessageCount += mid;
} else {
trucateMessageCount += it->second.size();
}
}
if (trucateMessageCount <= maxSize) {
return true;
}
return false;
}
public:
vector<LogMessage*>solve(vector<LogMessage*>&logMessages, int maxSize) {
unordered_map<string, vector<string>>m;
for(int i=0;i<logMessages.size();i++) {
string sourceName = logMessages[i]->sourceName;
string content = logMessages[i]->content;
m[sourceName].push_back(content);
}
int l = 1, r = 1E5;
int X;
while(l<=r) {
int mid = l + (r-l)/2;
if (check(m, mid, maxSize)) {
X = mid;
l = mid+1;
}else {
r = mid-1;
}
}
vector<LogMessage*>ans;
for(auto it = m.begin(); it!=m.end(); it++) {
string sourceName = it->first;
for(int i=0;i<min((int)X, (int)it->second.size());i++) {
string content = it->second[i];
ans.push_back(new LogMessage(sourceName, content));
}
}
return ans;
}
};
int main() {
LogMessage* m1 = new LogMessage("source_a", "m");
LogMessage* m2 = new LogMessage("source_a", "m");
LogMessage* m3 = new LogMessage("source_b", "m");
vector<LogMessage*>v = {m1, m2, m3};
int maxSize = 2;
Solution* solution = new Solution();
vector<LogMessage*> ans = solution->solve(v, maxSize);
for(int i=0;i<ans.size();i++) {
cout<<ans[i]->sourceName<<" "<<ans[i]->content<<endl;
}
}
