Link Sub: http://www.spoj.com/PTIT/problems/P144PROI/
Người Gửi: Loo?
- Problem:
Bạn được cho n đoạn thẳng trên tia Ox. Đoạn thứ i được bắt đầu từ điểm L[i] và kết thúc tại R[i]. Nhiệm vụ của bạn là tìm trong tập đoạn đã cho đoạn thẳng lớn nhất, bao trùm tất cả các tập đoạn còn lại. Hãy in ra chỉ số của đoạn thẳng đó, nếu không tồn tại thì in ra -1.
Đoạn [a,b] được gọi là bao trùm đoạn [c, d] nếu a <= c <= d <= b.
Input
Dòng đầu tiên là số nguyên n(1 <= n <= 100).
n dòng tiếp theo, mỗi dòng gồm 2 số nguyên L[i], R[i] (1<= L[i] <= R[i] <= 10^9) biểu diễn đoạn thứ i.
Các đoạn được đánh số bắt đầu 1.
Output
In ra một số nguyên duy nhất là đáp án của bài toán. Input đảm bảo không có 2 đoạn thẳng nào trùng nhau.
Example:
In ra một số nguyên duy nhất là đáp án của bài toán. Input đảm bảo không có 2 đoạn thẳng nào trùng nhau.
Input
3
1 1
2 2
3 3
Output:
-1
Input
6
1 5
2 3
1 10
7 10
7 7
10 10
Output:
3
- Solution:
Bao trùm tất cả có nghĩa là: Có một cặp left - right sao cho: left là nhỏ nhất và right là lớn nhất.
Vậy thì chỉ cần tìm left min và right max là được.
VD1:
1 1
2 3
left min = 1, right max = 3. Có nghĩa là phải có đoạn [1, 3] mới có thể bao trùm được tất cả. Nhưng không! Trên dãy kia không có đoạn [1, 3] nên in ra -1;
VD2:
2 3
1 9
left min = 1, right max = 9. Có nghĩa là phải có đoạn [1, 9] mới có thể bao trùm được tất cả. Vâng! Trên dãy kia có đoạn [1, 9] nên ta sẽ in ra vị trí của [1 9];Input
6
1 5
2 3
1 10
7 10
7 7
10 10
Output:
3