Created
September 20, 2021 23:36
-
-
Save lewismj/40193ea0c90d54c865c7684da0c1531c to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <map> | |
| #include <list> | |
| #include <stack> | |
| #include <algorithm> | |
| #include <vector> | |
| #include <future> | |
| #include <sstream> | |
| struct entry { | |
| int start; | |
| int end; | |
| int price; | |
| friend std::ostream& operator<<(std::ostream& os, const entry& e); | |
| }; | |
| std::ostream& operator<<(std::ostream& os, const entry& e) { | |
| os << "{" << e.start << "," << e.end << "," << e.price << "}"; | |
| return os; | |
| } | |
| template<typename T> std::string to_string(const T& xs, const std::string& delim=" ") { | |
| std::ostringstream os; | |
| for (const auto& x: xs) { | |
| if (&x != &xs[0]) os << delim; | |
| os << x; | |
| } | |
| return os.str(); | |
| } | |
| std::vector<entry> min_internals(std::vector<entry>& xs) { | |
| std::sort(xs.begin(), xs.end(), [](const entry &a, const entry &b) { return a.start < b.start; }); | |
| std::vector<entry> ys; | |
| std::stack<entry> s; | |
| for (const auto&x : xs) { // x is next interval to consider. | |
| if (s.empty()) s.push(x); | |
| else { | |
| entry top = s.top(); // copied. | |
| if ( x.start >= top.end ) { | |
| /* | |
| * ------------- (top) | |
| * ------------------ (x) | |
| */ | |
| s.push(x); | |
| } | |
| else { | |
| /* 1) | |
| * -------------- (top) | |
| * -------------- (x) | |
| * | |
| * 2) | |
| * -------------- | |
| * ------------------ (x) | |
| * | |
| * 3) | |
| * ----------------- (top) | |
| * ----------- (x) | |
| * | |
| * 4) | |
| * --------------- (top) | |
| * ------- (x) | |
| */ | |
| if ( top.price == x.price) { // in all 4 cases if the prices are equal merge them. | |
| s.pop(); | |
| s.push(entry { std::min(top.start,x.start), std::max(top.end,x.end), x.price}); | |
| } | |
| else { /* Could simplify the if logic, but it matches the 'geometry' of the cases. */ | |
| // case 1) | |
| if (x.start > top.start && x.end > top.end) { | |
| if (x.price < top.price) { | |
| s.pop(); | |
| s.push(entry{top.start, x.start, top.price}); | |
| s.push(entry{x.start, x.end, x.price}); | |
| } else { | |
| s.push(entry{top.end, x.end, x.price}); | |
| } | |
| } | |
| // case 2) | |
| if (x.start == top.start && x.end > top.end) { | |
| if (x.price < top.price) { | |
| s.pop(); | |
| s.push(entry{x.start, x.end, x.price}); | |
| } else { | |
| s.push(entry{top.end, x.end, x.price}); | |
| } | |
| } | |
| // case 3) | |
| if (x.start > top.start && x.end < top.end) { | |
| if (x.price < top.price) { | |
| s.pop(); | |
| s.push(entry{top.start, x.start, top.price}); | |
| s.push(entry{x.start, x.end, x.price}); | |
| s.push(entry{x.end, top.end, top.price}); | |
| } else { | |
| /* fully contained and more expensive, do nothing.*/ | |
| } | |
| } | |
| // case 4) | |
| if (x.start == top.start && x.end < top.end) { | |
| if (x.price < top.price) { | |
| s.pop(); | |
| s.push(entry{x.start, x.end, x.price}); | |
| s.push(entry{x.end, top.end, top.price}); | |
| } else { | |
| /* fully contained and more expensive, do nothing.*/ | |
| } | |
| } | |
| } | |
| } | |
| } | |
| }; | |
| while (!s.empty()) { ys.push_back(s.top()); s.pop(); } | |
| std::reverse(ys.begin(),ys.end()); | |
| return ys; | |
| } | |
| int main(int, char**) { | |
| /*std::vector<entry> xs = { {0,3,5}, {1,2,3}};*/ | |
| std::vector<entry> xs = { {0,4,5}, | |
| {2,8,3}, | |
| {7,11,10}}; | |
| // sort by ascending start date/cost. | |
| std::cout << to_string(min_internals(xs)) << std::endl; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment