/* * paint_sjz.cpp * * Created on: Oct 9, 2016 * Author: Steven Zeil */ #include #include #include using namespace std; struct Interval { long start; long stop; long bestSoFar; Interval() : start(0), stop(0), bestSoFar(0) {} Interval(long strt, long stp) : start(strt), stop(stp), bestSoFar(0) {} bool operator< (const Interval& intrv) const; bool operator== (const Interval& intrv) const; }; bool Interval::operator< (const Interval& intrv) const { if (stop != intrv.stop) return stop < intrv.stop; else return start < intrv.start; } bool Interval::operator== (const Interval& intrv) const { return (stop == intrv.stop) && (start == intrv.start); } ostream& operator<< (ostream& out, const Interval iv) { out << iv.start << ".." << iv.stop << ":" << iv.bestSoFar; return out; } void solve (Interval* interval, int k) { sort (interval, interval+k); interval[0].bestSoFar = interval[0].stop - interval[0].start; for (int i = 1; i <= k; ++i) { // Option 1 - do not use this interval long best1 = interval[i].bestSoFar = interval[i-1].bestSoFar; // Option 2. Use this interval with the best combination of intervals // up to the start of this one. Interval searchKey (interval[i].start, interval[i].start); Interval* earlierCase = lower_bound(interval, interval+i, searchKey); if (earlierCase != interval) { --earlierCase; } //cerr << "Looking back to " << *earlierCase << endl; long best2 = earlierCase->bestSoFar + interval[i].stop - interval[i].start; interval[i].bestSoFar = max(best1, best2); //cerr << i << " " << interval[i] << ": " << best1 << " " << best2 << endl; } cout << interval[k].bestSoFar << endl; } void solve (istream& in) { int k; in >> k; Interval* interval = new Interval[k+1]; interval[0] = Interval(0,0); for (int i = 0; i < k; ++i) { long x0, x1; in >> x0 >> x1; interval[i+1] = Interval(x0, x1); } solve (interval, k); delete [] interval; } int main (int argc, char** argv) { if (argc > 1) { for (int i = 1; i < argc; ++i) { ifstream in(argv[i]); solve (in); } } else { solve (cin); } }