## Thursday, June 9, 2016

### Contained Ranges - Coding in a Smart Way

Contained Ranges - Coding in a Smart Way
A range [x1, x2] is contained in a range [y1, y2] if y1 ≤ x1 ≤ x2 ≤ y2. Given a list of ranges A, check whether there exists a pair of ranges such that one range is contained in the other range.

Since the condition of range [x1, x2] is contained in range [y1, y2] is that y1 ≤ x1 ≤ x2 ≤ y2, we want to sort ranges by start of range in increasing order. Sorting only takes O(NlogN).
Yes we can. Given A[i], do we need to check all A[j] where j < i whether A[i] is contained in A[j]? Actually, it is sufficient to check whether A[i] is contained in A[i-1]. Given any range A[j] before A[i-1], since A[i-1] is not contained by A[j], the end of range A[i-1] must greater than the end of range A[j]. Therefore, if A[i] is contained in A[j], it is also contained in A[i-1]. This is similar to the range [7, 8] is contained in [5, 9] and also [6, 10].
`public` `class` `Range{`
`    ``public` `int` `start;`
`    ``public` `int` `end;`
`    ``public` `Range(``int` `s, ``int` `e){`
`        ``start = s;`
`        ``end = e;`
`    ``}`
`    `
`    ``@Override`
`    ``public` `String toString() {`
`        ``return` `"["` `+ start + ``","` `+ end + ``"]"``;`
`    ``}`
`    `
`    ``@Override`
`    ``public` `boolean` `equals(Object o) {  `
`        ``if` `(o == ``this``) {`
`            ``return` `true``;`
`        ``}`
`        ``if` `(!(o ``instanceof` `Range)) {`
`            ``return` `false``;`
`        ``}`
`        ``Range c = (Range) o;`
`        ``return` `start == c.start && end == c.end;             `
`    ``}`
`}`
`//compare two range by start, used to sort list of ranges by their starts`
`public` `class` `RangeComparator ``implements` `Comparator<Range> {`
`    ``public` `int` `compare(Range range1, Range range2) { `
`        ``return` `Integer.compare(range1.start, range2.start);`
`    ``}`
`}`
`public` `boolean` `hasContainedRange(List<Range> ranges){`
`    ``if` `(ranges.size() < ``2``){`
`        ``return` `false``;`
`    ``}`
`    `
`    ``ranges.sort(``new` `RangeComparator());`
`    ``for``(``int` `i = ``1``; i < ranges.size(); i++) {`
`        ``if` `(ranges.get(i).end <= ranges.get(i - ``1``).end){`
`            ``return` `true``;`
`        ``}`
`    ``}`
`    `
`    ``return` `false``;`
`}`