{"id":9143,"date":"2021-12-12T14:07:45","date_gmt":"2021-12-12T22:07:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9143"},"modified":"2021-12-12T14:18:48","modified_gmt":"2021-12-12T22:18:48","slug":"leetcode-2102-sequentially-ordinal-rank-tracker","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-2102-sequentially-ordinal-rank-tracker\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2102. Sequentially Ordinal Rank Tracker"},"content":{"rendered":"\n<p>A scenic location is represented by its&nbsp;<code>name<\/code>&nbsp;and attractiveness&nbsp;<code>score<\/code>, where&nbsp;<code>name<\/code>&nbsp;is a&nbsp;<strong>unique<\/strong>&nbsp;string among all locations and&nbsp;<code>score<\/code>&nbsp;is an integer. Locations can be ranked from the best to the worst. The&nbsp;<strong>higher<\/strong>&nbsp;the score, the better the location. If the scores of two locations are equal, then the location with the&nbsp;<strong>lexicographically smaller<\/strong>&nbsp;name is better.<\/p>\n\n\n\n<p>You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Adding<\/strong>&nbsp;scenic locations,&nbsp;<strong>one at a time<\/strong>.<\/li><li><strong>Querying<\/strong>&nbsp;the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;<strong>best<\/strong>&nbsp;location of&nbsp;<strong>all locations already added<\/strong>, where&nbsp;<code>i<\/code>&nbsp;is the number of times the system has been queried (including the current query).<ul><li>For example, when the system is queried for the&nbsp;<code>4<sup>th<\/sup><\/code>&nbsp;time, it returns the&nbsp;<code>4<sup>th<\/sup><\/code>&nbsp;best location of all locations already added.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Note that the test data are generated so that&nbsp;<strong>at any time<\/strong>, the number of queries&nbsp;<strong>does not exceed<\/strong>&nbsp;the number of locations added to the system.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>SORTracker<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>SORTracker()<\/code>&nbsp;Initializes the tracker system.<\/li><li><code>void add(string name, int score)<\/code>&nbsp;Adds a scenic location with&nbsp;<code>name<\/code>&nbsp;and&nbsp;<code>score<\/code>&nbsp;to the system.<\/li><li><code>string get()<\/code>&nbsp;Queries and returns the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;best location, where&nbsp;<code>i<\/code>&nbsp;is the number of times this method has been invoked (including this invocation).<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:true\"><strong>Input<\/strong>\n[\"SORTracker\", \"add\", \"add\", \"get\", \"add\", \"get\", \"add\", \"get\", \"add\", \"get\", \"add\", \"get\", \"get\"]\n[[], [\"bradford\", 2], [\"branford\", 3], [], [\"alps\", 2], [], [\"orland\", 2], [], [\"orlando\", 3], [], [\"alpine\", 2], [], []]\n<strong>Output<\/strong>\n[null, null, null, \"branford\", null, \"alps\", null, \"bradford\", null, \"bradford\", null, \"bradford\", \"orland\"]\n<p><strong>Explanation<\/strong> \nSORTracker tracker = new SORTracker(); \/\/ Initialize the tracker system.\ntracker.add(\"bradford\", 2);            \/\/ Add location with name=\"bradford\" and score=2 to the system.\ntracker.add(\"branford\", 3);            \/\/ Add location with name=\"branford\" and score=3 to the system.\ntracker.get();                         \/\/ The sorted locations, from best to worst, are: branford, bradford. \n                                       \/\/ Note that branford precedes bradford due to its <strong>higher score<\/strong> (3 &gt; 2). \n                                       \/\/ This is the 1<sup>st<\/sup> time get() is called, so return the best location: \"branford\". \ntracker.add(\"alps\", 2);                \/\/ Add location with name=\"alps\" and score=2 to the system.\ntracker.get();                         \/\/ Sorted locations: branford, alps, bradford. \n                                       \/\/ Note that alps precedes bradford even though they have the same score (2). \n                                       \/\/ This is because \"alps\" is <strong>lexicographically smaller<\/strong> than \"bradford\". \n                                       \/\/ Return the 2<sup>nd<\/sup> best location \"alps\", as it is the 2<sup>nd<\/sup> time get() is called.\ntracker.add(\"orland\", 2);              \/\/ Add location with name=\"orland\" and score=2 to the system.\ntracker.get();                         \/\/ Sorted locations: branford, alps, bradford, orland. \n                                       \/\/ Return \"bradford\", as it is the 3<sup>rd<\/sup> time get() is called. \ntracker.add(\"orlando\", 3);             \/\/ Add location with name=\"orlando\" and score=3 to the system.\ntracker.get();                         \/\/ Sorted locations: branford, orlando, alps, bradford, orland. \n                                       \/\/ Return \"bradford\". \ntracker.add(\"alpine\", 2);              \/\/ Add location with name=\"alpine\" and score=2 to the system.\ntracker.get();                         \/\/ Sorted locations: branford, orlando, alpine, alps, bradford, orland. \n                                       \/\/ Return \"bradford\". \ntracker.get();                         \/\/ Sorted locations: branford, orlando, alpine, alps, bradford, orland. \n                                       \/\/ Return \"orland\".\n<\/p>\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>name<\/code>&nbsp;consists of lowercase English letters, and is unique among all locations.<\/li><li><code>1 &lt;= name.length &lt;= 10<\/code><\/li><li><code>1 &lt;= score &lt;= 10<sup>5<\/sup><\/code><\/li><li>At any time, the number of calls to&nbsp;<code>get<\/code>&nbsp;does not exceed the number of calls to&nbsp;<code>add<\/code>.<\/li><li>At most&nbsp;<code>4 * 10<sup>4<\/sup><\/code>&nbsp;calls&nbsp;<strong>in total<\/strong>&nbsp;will be made to&nbsp;<code>add<\/code>&nbsp;and&nbsp;<code>get<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: TreeSet w\/ Iterator<\/strong><\/h2>\n\n\n\n<p>Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it&#8217;s higher than the current element then let the iterator go backward one step. <\/p>\n\n\n\n<p>Time complexity:  add O(logn) \/ get O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass SORTracker {\npublic:\n  SORTracker() {}\n\n  void add(string name, int score) {    \n    if (*s.emplace(-score, name).first < *cit) --cit;\n  }\n\n  string get() {\n    return (cit++)->second;\n  }\nprivate:\n  set<pair<int, string>> s;\n  \/\/ Note: cit points to begin(s) after first insertion.\n  set<pair<int, string>>::const_iterator cit = end(s);\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A scenic location is represented by its&nbsp;name&nbsp;and attractiveness&nbsp;score, where&nbsp;name&nbsp;is a&nbsp;unique&nbsp;string among all locations and&nbsp;score&nbsp;is an integer. Locations can be ranked from the best to the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[291,217,625,243,656],"class_list":["post-9143","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-data-structure","tag-hard","tag-iterator","tag-set","tag-treeset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9143","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9143"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9143\/revisions"}],"predecessor-version":[{"id":9155,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9143\/revisions\/9155"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9143"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}