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.
Read full article from 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
;
}