Cần giúp đỡ bài toán về khoảng thời gian

Chào các bác, em mới học c++ thì gặp bài tập này nhưng chưa hiểu rõ đề nên chưa làm được, bác nào có thể giúp em với không ạ?

Bài này có thể hiểu đơn giản là “tìm số lần xuất hiện nhiều nhất của các phần tử trong mảng”, nhưng thay vì cho trực tiếp các phần tử, thì nó cho theo đoạn, nên có thể có cách nào đó nhanh hơn :thinking:

2 Likes
  1. tạo một mảng t[n]. t[i] = số học sinh có mặt tại thời điểm i => đáp án là max©
  2. học sinh i có mặt từ thời điểm a[i] đến b[i] thì tăng tất cả t[x] lên 1 với a[i] <= x <= b[i]

tuy nhiên nếu bước 2 làm vậy thì sẽ tạch các testcase lớn
không biết giải thuật này có tên không, nhưng concept là thế này
tăng đoạn từ a tới b lên 1 thi sẽ có sự chênh lệch giữa phần tử t[a] và t[a-1] sẽ tăng lên 1, cụ thể:
học sinh i có mặt từ thời đểm t = 7 đến t = 10
thì trong mảng t, bạn phải tăng gía trị của phần tử 7 8 9 10 trong mảng t lên 1 đơn vị
như vậy,

  1. độ lệch d của t[7] so với t[6] tăng lên một, gọi độ lệch đó là d[i] luôn, tức là d[7] += 1
  2. đọ lệch d’ của t[10] so với t[11] tăng lên 1, hay nói cách khác độ lệch của t[11] so với t[10] giảm 1, d[11] -= 1, vì khi tăng đoạn từ 7 tới 10, sẽ làm thằng t[11] nhỏ hơn thêm 1 đơn vị so với 10

sau khi tính xong đọ lệch O(n) thì ta có công thức
t[i] = t[i-1] + d[i], số học sinh có mặt tại thời điểm t[i] bằng với số học sinh tại thời điểm t[i-1] cộng với độ lệnh giữa 2 thời điểm

chốt O(n).

Giải thích:
bạn cần biết tại thời điểm t = 3 có bao nhiêu học sinh có mặt?
bạn đã biết được tại thời điểm t = 2 có 7 học sinh có mặt
và thời điểm t = 3 có nhiều hơn thời điểm t = 2 là 4 học sinh
=> kết quả t = 3 có 11 học sinh

bạn cần biết tại thời điểm t = 8 có bao nhiêu học sinh có mặt?
bạn đã biết được tại thời điểm t = 7 có 10 học sinh có mặt
và thời điểm t = 8 có nhiều hơn thời điểm t = 7 là -1 học sinh
=> kết quả t = 8 có 9 học sinh

cái này gọi là phương pháp quy hoạch động, không phải là giải thuật

6 Likes

VD: [7, 10] có thể hiểu là đến lúc 7 giờ và rời đi lúc 11 giờ. Vậy ta ghi nhận số người đến trừ số người đi vào mỗi thời điểm :slight_smile:

Thực ra cách trên là O(n+l) time và O(l) space. Một cách làm khác là trích thời gian đến và thời gian đi thành hai mảng và sắp xếp, với chỉ O(n) space, được xem là tốt hơn vì thời gian có thể set lên 10^9 :D, hay độ phức tạp chỉ phụ thuộc độ dài input, chứ không phụ thuộc con số trong nó.

var f = intervals => {
   var g = (f, things) => thing.map(f).sort();
   var arrivals = g(thing => thing[0], intervals);
   var departures = g(thing => 1+thing[1], intervals);
   return [arrivals, departures];
}
6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?