Given a list of integers, find out the biggest interval that has all its members in the given list. e.g. given list 1, 7, 4, 6, 3, 10, 2 then answer would be [1, 4]. Develop algorithm and write code for this
-------------------------------------------------------------------------
What is biggest interval? It means the longest consecutive integers. Take the above example, 1, 2, 3, 4 are members of the list.
#include<iostream> #include<stdio.h> #include<stack> #include<vector> #include<string> #include<unordered_set> #include<unordered_map> #include<set> #include<queue> #include<map> using namespace std; class Solution { public: void largestRange(vector<int>& lst, vector<int>& range) { unordered_set<int> table; range[0] = 0; range[1] = -1; int size = lst.size(), i, j, cur, a, b; for (i = 0; i < size; ++i) table.insert(lst[i]); for (unordered_set<int>::iterator it = table.begin(); table.size() > 0; it = table.begin()) { cur = *it; table.erase(it); for (i = cur + 1; table.size() > 0; ++i) { if (table.find(i) == table.end()) break; table.erase(i); } b = i - 1; for (j = cur - 1; table.size() > 0; --j) { if (table.find(j) == table.end()) break; table.erase(j); } a = j + 1; if (b - a > range[1] - range[0]) { range[1] = b; range[0] = a; } } } }; int main() { Solution s; int a[] = {1, 7, 4, 6, 3, 10, 2}; vector<int> v(a, a + 7); vector<int> range(2); s.largestRange(v, range); cout<<range[0]<<" "<<range[1]<<endl; return 0; }
CareerCup Find the biggest interval that has all its members in list in O(n)