Bài 34.2. Thời Gian Hoạt Động Của Mạng Lưới - Độ khó: Khá

Một công ty viễn thông cần phân tích thời gian hoạt động của các thiết bị mạng. Mỗi thiết bị được ghi nhận thời gian bắt đầu hoạt động \(S_i\) và thời gian kết thúc hoạt động \(T_i\). Giả sử thời gian được đo bằng giây và chỉ có thể là các số nguyên dương từ 1 đến \(M\). Công ty muốn biết tại bất kỳ thời điểm nào từ 1 đến \(M\), có bao nhiêu thiết bị đang hoạt động đồng thời. Đặc biệt, họ quan tâm đến thời điểm có số lượng thiết bị hoạt động đồng thời cao nhất.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(1 \le M \le 10^6\)) - số lượng thiết bị và thời điểm tối đa. \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S_i\) và \(T_i\) (\(1 \le S_i \le T_i \le M\)) - thời gian bắt đầu và kết thúc hoạt động của thiết bị thứ \(i\).

OUTPUT FORMAT

In ra một số nguyên duy nhất là số lượng thiết bị hoạt động đồng thời cao nhất tại bất kỳ thời điểm nào trong khoảng từ 1 đến \(M\).

Ví dụ:

Input:

4 10
1 5
3 7
2 4
6 9

Output:

3

Giải thích:

• Khởi tạo một mảng diff kích thước \(M+2\) với tất cả các giá trị là 0.
• Với mỗi khoảng thời gian \([S_i, T_i]\):
  • Tăng diff[S_i] lên 1 (thiết bị bắt đầu hoạt động).
  • Giảm diff[T_i + 1] xuống 1 (thiết bị kết thúc hoạt động sau thời điểm \(T_i\)).
• Sau khi xử lý tất cả các khoảng, ta có mảng diff:
  • Thiết bị 1: [1, 5] -> diff[1]++, diff[6]--
  • Thiết bị 2: [3, 7] -> diff[3]++, diff[8]--
  • Thiết bị 3: [2, 4] -> diff[2]++, diff[5]--
  • Thiết bị 4: [6, 9] -> diff[6]++, diff[10]--

Mảng diff (chỉ những vị trí thay đổi): diff[1]=1, diff[2]=1, diff[3]=1, diff[5]=-1, diff[6]=0 (1 - 1 = 0), diff[8]=-1, diff[10]=-1

• Xây dựng mảng current_active bằng cách tính tổng tiền tố của diff:

  • Thời điểm 1: current_active[1] = diff[1] = 1
  • Thời điểm 2: current_active[2] = current_active[1] + diff[2] = 1 + 1 = 2
  • Thời điểm 3: current_active[3] = current_active[2] + diff[3] = 2 + 1 = 3
  • Thời điểm 4: current_active[4] = current_active[3] + diff[4] = 3 + 0 = 3
  • Thời điểm 5: current_active[5] = current_active[4] + diff[5] = 3 + (-1) = 2
  • Thời điểm 6: current_active[6] = current_active[5] + diff[6] = 2 + 0 = 2
  • Thời điểm 7: current_active[7] = current_active[6] + diff[7] = 2 + 0 = 2
  • Thời điểm 8: current_active[8] = current_active[7] + diff[8] = 2 + (-1) = 1
  • Thời điểm 9: current_active[9] = current_active[8] + diff[9] = 1 + 0 = 1
  • Thời điểm 10: current_active[10] = current_active[9] + diff[10] = 1 + (-1) = 0

• Các giá trị current_active từ thời điểm 1 đến 10 là: [1, 2, 3, 3, 2, 2, 2, 1, 1, 0].

• Giá trị lớn nhất trong mảng current_active là 3.