[LintCode]Digital Coverage

给定一堆interval，每个interval的起始为start，终点为end，start和end均为整数，其cover[start, end]的区间。求哪个数被覆盖的次数最多，如果最多的有多个输出最小的那个。这道题和Meeting Rooms II是一样的，我么 用一根线从左向右扫，与所有interval相交最多的点就是答案。时间复杂度空间复杂度均为O(n)，代码如下：

	class Solution {
	public:
	/**
	* @param intervals: The intervals
	* @return: The answer
	*/
	int digitalCoverage(vector<Interval> &intervals) {
	map<int, int> cnts;
	for (auto& interval : intervals)
	{
	int start = interval.start, end = interval.end;
	++cnts[start];
	--cnts[end + 1];
	}
	int res = 0, maxCnt = 0, currCnt = 0;
	for (const auto& cnt : cnts)
	{
	currCnt += cnt.second;
	if (currCnt > maxCnt)
	{
	maxCnt = currCnt;
	res = cnt.first;
	}
	}
	return res;
	}
	};

view raw Digital Coverage.cpp hosted with ❤ by GitHub