Skip to content

Instantly share code, notes, and snippets.

@webglider

webglider/vhsrec.cc

Created Dec 12, 2015
Embed
What would you like to do?
Daily programmer challenge 242 Intermediate
// https://www.reddit.com/r/dailyprogrammer/comments/3u6o56/20151118_challenge_242_intermediate_vhs_recording/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Show {
public:
int id, start, end;
string name;
Show(int _start, int _end, string _name) {
start = _start;
end = _end;
name = _name;
}
bool intersects(Show& other) {
return ( other.start < end &&
other.end > start );
}
};
bool show_starts_before(const Show& a, const Show& b) {
return (a.start < b.start);
}
bool show_ends_before(const Show& a, const Show& b) {
return (a.end < b.end);
}
int main() {
ifstream ifile("inp.txt");
int x,y;
string name, fav;
vector<Show> shows;
getline(ifile, fav);
while(ifile >> x >> y) {
getline(ifile >> ws, name);
Show buf_show (x,y,name);
buf_show.id = shows.size();
shows.push_back(buf_show);
}
// find start and end points of favourite show
int fav_id;
for(auto show : shows)
if(show.name == fav)
fav_id = show.id;
// final schedule
vector<bool> final (shows.size(), 1);
// get rid of all shows that collide with favourite
for(auto show : shows)
if(show.id != fav_id &&
show.intersects(shows[fav_id]))
final[ show.id ] = 0;
// sort by start and end point
vector<Show> start_sorted = shows
, end_sorted = shows;
sort(start_sorted.begin(), start_sorted.end(), show_starts_before);
sort(end_sorted.begin(), end_sorted.end(), show_ends_before);
// greedily select from end sorted array
int n = shows.size(), start_idx = 0;
for(auto show : end_sorted) {
if(!final[ show.id ]) continue;
// delete all intersecting intervals
while(start_idx < n &&
show.intersects(start_sorted[start_idx]) ) {
if(start_sorted[start_idx].id != show.id)
final[start_sorted[start_idx].id] = 0;
start_idx++;
}
}
// print the final schedule
for(auto show : shows) {
if(final[ show.id ])
cout << show.name << "\n";
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.