2276. Count Integers in Intervals Hard
1/**
2 * [2276] Count Integers in Intervals
3 *
4 * Given an empty set of intervals, implement a data structure that can:
5 *
6 * Add an interval to the set of intervals.
7 * Count the number of integers that are present in at least one interval.
8 *
9 * Implement the CountIntervals class:
10 *
11 * CountIntervals() Initializes the object with an empty set of intervals.
12 * void add(int left, int right) Adds the interval [left, right] to the set of intervals.
13 * int count() Returns the number of integers that are present in at least one interval.
14 *
15 * Note that an interval [left, right] denotes all the integers x where left <= x <= right.
16 *
17 * Example 1:
18 *
19 * Input
20 * ["CountIntervals", "add", "add", "count", "add", "count"]
21 * [[], [2, 3], [7, 10], [], [5, 8], []]
22 * Output
23 * [null, null, null, 6, null, 8]
24 * Explanation
25 * CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.
26 * countIntervals.add(2, 3); // add [2, 3] to the set of intervals.
27 * countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
28 * countIntervals.count(); // return 6
29 * // the integers 2 and 3 are present in the interval [2, 3].
30 * // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
31 * countIntervals.add(5, 8); // add [5, 8] to the set of intervals.
32 * countIntervals.count(); // return 8
33 * // the integers 2 and 3 are present in the interval [2, 3].
34 * // the integers 5 and 6 are present in the interval [5, 8].
35 * // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
36 * // the integers 9 and 10 are present in the interval [7, 10].
37 *
38 *
39 * Constraints:
40 *
41 * 1 <= left <= right <= 10^9
42 * At most 10^5 calls in total will be made to add and count.
43 * At least one call will be made to count.
44 *
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/count-integers-in-intervals/
49// discuss: https://leetcode.com/problems/count-integers-in-intervals/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53#[derive(Debug)]
54struct CountIntervals {
55 count: i32,
56 intervals: Vec<(i32, i32)>,
57}
58
59/**
60 * `&self` means the method takes an immutable reference.
61 * If you need a mutable reference, change it to `&mut self` instead.
62 */
63impl CountIntervals {
64 fn new() -> Self {
65 CountIntervals {
66 count: 0,
67 intervals: vec![],
68 }
69 }
70
71 fn just_add(&mut self, index: usize, left: i32, right: i32) {
72 self.intervals.insert(index, (left, right));
73 self.count += right - left + 1;
74 }
75
76 fn just_remove(&mut self, index: usize) {
77 self.count -= self.intervals[index].1 - self.intervals[index].0 + 1;
78 self.intervals.remove(index);
79 }
80
81 fn add(&mut self, left: i32, right: i32) {
82 if self.intervals.is_empty() {
83 self.just_add(0, left, right);
84 println!("After add {}, {}, we got {:#?}", left, right, self);
85 return;
86 }
87
88 let low = self.find_low(left);
89 println!("adding {}, {}, low {}", left, right, low);
90 if low == self.intervals.len() {
91 self.just_add(low, left, right);
92 println!("After add {}, {}, we got {:#?}", left, right, self);
93 return;
94 }
95 let mut n_l = left;
96 let mut n_r = right;
97 let mut i = low;
98
99 loop {
100 //println!("in1 add {}, {}, we got {:#?} all {:#?}", left, right, i, self);
101 if i >= self.intervals.len() {
102 break;
103 }
104 let x = self.intervals[i];
105 //println!("in add {}, {}, we got {:#?} when {} all {:#?}", left, right, x, i, self);
106 if x.1 >= left && x.0 < right || x.0 <= right && x.1 > left || left <= x.0 && right >= x.1 {
107 n_l = if n_l < self.intervals[i].0 {
108 n_l
109 } else {
110 self.intervals[i].0
111 };
112 n_r = if n_r > self.intervals[i].1 {
113 n_r
114 } else {
115 self.intervals[i].1
116 };
117 self.just_remove(i);
118 //println!("in 2 add {}, {}, we got {:#?} when {} all {:#?}", left, right, x, i, self);
119 continue;
120 } else if x.1 < left {
121 break;
122 }
123 i += 1;
124 }
125
126 self.just_add(low, n_l, n_r);
127
128 println!("After add {}, {}, we got {:#?}", left, right, self)
129 }
130
131 fn count(&self) -> i32 {
132 self.count
133 }
134
135 fn find_low(&self, left: i32) -> usize {
136 let mut s = 0;
137 let mut e = self.intervals.len();
138
139 while s < e {
140 let m = (s + e) / 2;
141 if self.intervals[m].1 < left {
142 s = m + 1
143 } else if self.intervals[m].0 > left {
144 if m == 0 {
145 return 0;
146 }
147 e = m
148 } else {
149 return m;
150 }
151 }
152
153 s
154 }
155}
156
157/**
158 * Your CountIntervals object will be instantiated and called as such:
159 * let obj = CountIntervals::new();
160 * obj.add(left, right);
161 * let ret_2: i32 = obj.count();
162 */
163
164// submission codes end
165
166#[cfg(test)]
167mod tests {
168 use super::*;
169
170 #[test]
171 fn test_2276_1() {
172 let mut c = CountIntervals::new();
173 c.add(2, 3);
174 c.add(7, 10);
175 assert_eq!(c.count(), 6);
176 c.add(5, 8);
177 assert_eq!(c.count(), 8);
178 c.add(3, 100);
179 assert_eq!(c.count(), 99);
180 c.add(0, 5);
181 assert_eq!(c.count(), 101);
182 c.add(101, 105);
183 c.add(107, 115);
184 c.add(121, 145);
185 assert_eq!(c.count(), 140);
186 }
187
188 #[test]
189 fn test_2276_2() {
190 let mut c = CountIntervals::new();
191 assert_eq!(c.count(), 0);
192 c.add(33, 49);
193 c.add(43, 47);
194 assert_eq!(c.count(), 17);
195 assert_eq!(c.count(), 17);
196 c.add(37, 37);
197 c.add(26, 38);
198 c.add(11, 11);
199 assert_eq!(c.count(), 25);
200 }
201
202 #[test]
203 fn test_2276_3() {
204 let mut c = CountIntervals::new();
205 c.add(616, 659);
206 c.add(913, 936);
207 c.add(6, 97);
208 c.add(949, 967);
209 c.add(315, 942);
210 c.add(380, 484);
211 c.add(66, 172);
212 c.add(737, 877);
213 assert_eq!(c.count(), 814);
214 }
215}
216Back
© 2025 bowen.ge All Rights Reserved.