Amazon Campus(2013-Sep-22)Question 1 / 2 (Amazon Campus(5): completely inside interval)
Question 1 / 2 (Amazon Campus(5): completely inside interval)

Given a set of open intervals, check whether there exists an interval which is completely inside another interval. If exists, print “1”, otherwise print “0”. You just need to consider the case that all the end points are integers and there are no exactly the same open intervals.

Input:

n --- number of open intervals

a_1 b_1 a_2 b_2 ... a_n b_n ------ n open intervals (a_1, b_1) ... (a_n, b_n), in which a_i < b_i for all i

Output:

1 (meaning that there exists an interval which is completely inside another interval) or 0 (otherwise)

Sample Input 1

3

1 2 3 4 5 6

Sample Output 1

0

Sample Input 2

2

1 4 2 3

Sample Output 2

1

    static int interval(int[] a) {        // a : storing all the end points, in the same order as the input, that is, a_1 b_1 a_2 b_2 ... a_n b_n        // return value: 1 (meaning that there exists an interval which is completely inside another interval) or 0 (otherwise)        int flag = 0;    for(int i=0; i<a.length-1; i+=2) {    for(int j=0; j!=i&&j<a.length-1; j+=2) {    if((a[i]<=a[j] && a[i+1]>=a[j+1]) || (a[j]<=a[i] && a[j+1]>=a[i+1])) {    flag = 1;    break;    }    }    }    return flag;    }

1楼ddd12121昨天 18:30

感觉，先把区间按先a后b的顺序排序好。然后应该可以O(n)扫过。总复杂度是O(nlgn)，比这个方法要好点。。。

Re: kingzone_2008昨天 23:47

回复ddd12121n嗯，理论上是这样，但是实际上上述做法也有剪枝，只是在最坏的情况下效率较低。

Re: kingzone_2008昨天 23:49

回复ddd12121n是的

Re: kingzone_2008昨天 23:49

回复kingzone_2008n嗯，理论上是这样，但是实际上上述做法也有剪枝，只是在最坏的情况下效率较低。