Skip to content

Instantly share code, notes, and snippets.

@lmaresz
Last active December 16, 2015 22:59
Show Gist options
  • Save lmaresz/c6ddd4745951bc082bee to your computer and use it in GitHub Desktop.
Save lmaresz/c6ddd4745951bc082bee to your computer and use it in GitHub Desktop.
1555 1630
1600 1635
1600 1640
1610 1640
1625 1720
1635 1720
1645 1740
1650 1720
1710 1730
1715 1810
1720 1740
1725 1810
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
void split (string &txt, vector<int> &out, char ch);
void search_solution (vector <vector <int>> data, int maximum, int x, vector <int> &push);
int search_max (vector <int> target);
int main()
{
vector <int> push;
vector <vector <int>> data;
string line;
ifstream input;
input.open("input.txt",ios::in);
while (getline(input,line)) {
vector <int> line_vector;
split (line, line_vector, ' ');
data.push_back(line_vector);
}
/* DEBUG PRINT
for (unsigned int i = 0; i < data.size(); i++) {
cout << i+1 << ". elem: " << data[i][0] << ">>" << data[i][1] << " length: " << data[i][2] << endl;
}
*/
int max_main = 0;
search_solution(data, max_main, 0, push);
cout << search_max(push) << endl;
input.close();
return 0;
}
void split (string &txt, vector<int> &out, char ch) {
int i = 0;
while (true) {
if (txt[i] == ' ') {
string begin_str = txt.substr(0,i);
string end_str = txt.substr(i+1,txt.size()-i);
int begin_int = stoi(begin_str.substr(0,2))*60 + stoi(begin_str.substr(2,2));
int end_int = stoi(end_str.substr(0,2))*60 + stoi(end_str.substr(2,2));
out.push_back(begin_int);
out.push_back(end_int);
out.push_back(end_int-begin_int);
break;
}
i++;
}
}
void search_solution (vector <vector <int>> data, int maximum, int x, vector <int> &push) {
for (unsigned int i = x+1; i < data.size(); i++) {
if (data[x][1] <= data[i][0]) {
search_solution(data, maximum+1, i, push);
}
}
push.push_back(maximum+1);
}
int search_max (vector <int> target) {
int maximum = 0;
for (unsigned int i = 0; i < target.size(); i++) {
if (target[i] > maximum) {
maximum = target[i];
}
}
return maximum;
}
@z2s8
Copy link

z2s8 commented Dec 16, 2015

Great solution! You are awesome! :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment