Interval Search

Similar Problems:

Description

Given a List of intervals, the length of each interval is 1000, such as [500,1500], [2100,3100].Give a number arbitrarily and determine if the number belongs to any of the intervals.return True or False.

Example

Given: List = [[100,1100],[1000,2000],[5500,6500]] number = 6000 Return: True

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.

- Solution:

## Blog link: https://code.dennyzhang.com/interval-search ## Basic Ideas: ## Binarysearch won't work, since the intervals may overlap ## Complexity: Time O(n), Space O(1) class Solution: """ @param intervalList: @param number: @return: return True or False """ def isInterval(self, intervalList, number): for intv in intervalList: if intv[0] <= number <= intv[1]: return "True" return "False"