Biến đổi dãy 2

Đề bài: Sơn có một ma trận a được thiết lập như sau:

a[i].size()=2. (0 ≤ i < a.size()).
a[i][0] ≤ a[i][1].
Một lần biến đổi Sơn thực hiện các việc như sau:

Tăng tất cả a[i][0] lên x đơn vị cho đến khi tồn tại a[i][0]=a[i][1]
Xóa tất cả các phần tử mà a[i][0] = a[i][1]
Sơn muốn biết phải biến đổi bao nhiêu lần để a không còn phần tử nào.
Với a = [[1,2],[3,5],[2,4],[5,6]] thì kết quả = 2.
Giải thích:
Lần biến đổ thứ 1:
Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[2,2],[4,5],[3,4],[6,6]]
Xóa a[0] và a[3], a = [[4,5],[3,4]]
Lần biến đổi thứ 2:
Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[5,5],[4,4]
xóa a[0] và a[1], lúc đó a rỗng và kết thúc.
Với a = [[1,2],[2,3],[3,4]] thì kết quả = 1.
Đầu vào: Một số n là kích thước của mảng, một mảng 2 chiều kích thước n*2
Đầu ra: Số lần biến đổi để a không còn phần tử nào.
Chương trình mong muốn: O(nlogn)

Ví dụ:

input:
4
1 2
3 5
2 4
5 6
output:
2

input:
3
1 2
2 3
3 4
output:
1

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!