در این مطلب، ویدئو حذف فواصل تحت پوشش – Leetcode 1288 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:11:56
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,080 –> 00:00:01,680
همه به بازگشت خوش آمدید و بیایید
2
00:00:01,680 –> 00:00:03,520
امروز یک کد دقیق تر بنویسیم، بنابراین امروز بیایید
3
00:00:03,520 –> 00:00:05,759
مشکل را حل کنیم بازه های پوشیده شده را حذف
4
00:00:05,759 –> 00:00:07,919
کنیم به ما آرایه ای از
5
00:00:07,919 –> 00:00:10,719
بازه ها داده می شود و هر بازه اساساً
6
00:00:10,719 –> 00:00:12,960
یک دو نقطه یک نقطه چپ و یک
7
00:00:12,960 –> 00:00:15,360
نقطه راست است، بنابراین اگر فرض کنیم یک
8
00:00:15,360 –> 00:00:16,480
خط اعداد
9
00:00:16,480 –> 00:00:19,039
مانند این، پس می دانید بیایید
10
00:00:19,039 –> 00:00:21,920
این فواصل را در نظر بگیریم، به عنوان مثال یک تا
11
00:00:21,920 –> 00:00:24,800
چهار احتمالاً چیزی شبیه به
12
00:00:24,800 –> 00:00:26,960
این خواهد بود، از نقطه ی
13
00:00:26,960 –> 00:00:28,640
یک تا انتها به نقطه چهار می رسد، بنابراین
14
00:00:28,640 –> 00:00:30,800
فقط یک خط یک بعدی است و سپس ما
15
00:00:30,800 –> 00:00:32,960
یک دسته فواصل یک بعدی داشته باشید،
16
00:00:32,960 –> 00:00:35,440
بنابراین از این لیست فواصل،
17
00:00:35,440 –> 00:00:38,000
میخواهیم تمام فواصل زمانی را که
18
00:00:38,000 –> 00:00:41,360
با بازه دیگری پوشانده شده است حذف کنیم و سپس
19
00:00:41,360 –> 00:00:44,079
بازههای باقیمانده را برگردانیم، یک
20
00:00:44,079 –> 00:00:46,079
بازه به عنوان پوشانده شدن توسط یک بازه دیگر تعریف میشود،
21
00:00:46,079 –> 00:00:47,760
اگر میدانید بیایید بگوییم
22
00:00:47,760 –> 00:00:50,160
این یک بازه و با این بازه پوشانده می
23
00:00:50,160 –> 00:00:52,559
شود اگر و در واقع بیایید آن را
24
00:00:52,559 –> 00:00:54,640
بیرون بیاوریم، بنابراین فرض کنید از a
25
00:00:54,640 –> 00:00:56,960
تا b این یک بازه است و
26
00:00:56,960 –> 00:00:59,840
بازه دیگری از c تا a داریم، بنابراین از
27
00:00:59,840 –> 00:01:01,600
نظر
28
00:01:01,600 –> 00:01:04,640
فنی بازه ای دیگری را می پوشاند، بنابراین
29
00:01:04,640 –> 00:01:07,040
در این مورد این بازه، این فاصله را می پوشاند
30
00:01:07,040 –> 00:01:10,560
زیرا نقطه c
31
00:01:10,560 –> 00:01:13,040
کمتر یا مساوی با نقطه a است و نقطه d
32
00:01:13,040 –> 00:01:16,880
بزرگتر یا مساوی نقطه b
33
00:01:16,880 –> 00:01:19,520
است، بنابراین اساساً uh برای این
34
00:01:19,520 –> 00:01:22,159
بازه پوشاننده باشد. در این یکی، نقاط
35
00:01:22,159 –> 00:01:25,200
باید مساوی باشند یا اوه، می دانید که این
36
00:01:25,200 –> 00:01:27,920
فاصله باید حتی بزرگتر از فاصله ای باشد که در
37
00:01:27,920 –> 00:01:30,560
آن پوشش می دهد، می دانید هر دو نقطه
38
00:01:30,560 –> 00:01:32,720
سمت راست باید برابر باشند یا
39
00:01:32,720 –> 00:01:34,320
می دانید که بیشتر از آن را پوشش می دهید، بنابراین
40
00:01:34,320 –> 00:01:35,840
کاملاً شهودی است که معنای آن چیست
41
00:01:35,840 –> 00:01:38,000
از آنجایی که به
42
00:01:38,000 –> 00:01:39,680
شما لیستی از فواصل را میدانید، بیایید نگاهی
43
00:01:39,680 –> 00:01:42,399
به این مثال بیندازیم که چه چیزی را
44
00:01:42,399 –> 00:01:44,000
برمیگردانیم، بنابراین نیروی بیرحم فقط برای نگاه کردن
45
00:01:44,000 –> 00:01:45,360
به تک تک بازهها باشد، بنابراین بیایید به
46
00:01:45,360 –> 00:01:47,280
این یکی نگاه کنیم که به خوبی پوشش داده شده است.
47
00:01:47,280 –> 00:01:48,720
باید در بازههای باقیمانده
48
00:01:48,720 –> 00:01:50,799
در لیست تکرار شود، این بازه
49
00:01:50,799 –> 00:01:53,759
این یک را پوشش میدهد، خیر، این فاصله
50
00:01:53,759 –> 00:01:56,079
این یک را پوشش میدهد، بنابراین این
51
00:01:56,079 –> 00:01:58,399
بازه پوشش داده نمیشود، این
52
00:01:58,399 –> 00:02:00,719
فاصله به خوبی پوشش داده میشود، این
53
00:02:00,719 –> 00:02:02,719
فاصله تعریف شده است به طور کلی آن را نمی پوشاند
54
00:02:02,719 –> 00:02:05,439
زیرا اگرچه این نقطه
55
00:02:05,439 –> 00:02:07,520
کمتر یا مساوی با این نقطه است، این نقطه
56
00:02:07,520 –> 00:02:09,520
بزرگتر یا مساوی این
57
00:02:09,520 –> 00:02:11,440
نقطه نیست، بنابراین این
58
00:02:11,440 –> 00:02:13,440
فاصله این نقطه را پوشش نمی دهد،
59
00:02:13,440 –> 00:02:16,239
این فاصله این نقطه را پوشش می دهد
60
00:02:16,239 –> 00:02:18,160
، نقطه سمت چپ آن کمتر از یا برابر با این
61
00:02:18,160 –> 00:02:20,000
یکی، نقطه سمت راست آن بزرگتر یا
62
00:02:20,000 –> 00:02:22,640
مساوی با این یکی است، بنابراین بله، این فاصله
63
00:02:22,640 –> 00:02:25,200
با این یکی پوشانده می شود،
64
00:02:25,200 –> 00:02:27,120
بنابراین می توانیم
65
00:02:27,120 –> 00:02:31,040
این فاصله را حذف کنیم، اگر این بازه
66
00:02:31,040 –> 00:02:32,080
پوشانده شده است
67
00:02:32,080 –> 00:02:33,440
، به تنها بازه باقی مانده نگاه می
68
00:02:33,440 –> 00:02:36,080
کنیم، خیر، این نیست پس این همان
69
00:02:36,080 –> 00:02:37,519
چیزی است که ما بر می گردانیم این دو
70
00:02:37,519 –> 00:02:38,879
بازه باقیمانده هستند و در
71
00:02:38,879 –> 00:02:40,239
واقع قرار نیست فواصل زمانی را برگردانیم،
72
00:02:40,239 –> 00:02:41,440
در واقع
73
00:02:41,440 –> 00:02:43,599
تعداد بازه های باقیمانده ای را که با سه شروع کرده ایم را برمی
74
00:02:43,599 –> 00:02:46,720
گردانیم، اکنون فقط دو بازه یک
75
00:02:46,720 –> 00:02:47,920
لبه داریم. شما ممکن است به این فکر
76
00:02:47,920 –> 00:02:49,599
کنید که اگر فواصل تکراری
77
00:02:49,599 –> 00:02:51,040
داشتیم دقیقاً مانند این بازه زمانی و
78
00:02:51,040 –> 00:02:52,720
چه میشد اگر دقیقاً
79
00:02:52,720 –> 00:02:54,800
شبیه آن بود و در واقع نمیتوانیم این را
80
00:02:54,800 –> 00:02:56,480
داشته باشیم زیرا ما گفته شد که
81
00:02:56,480 –> 00:02:59,040
هیچ بازهای تکراری وجود نخواهد داشت، دو
82
00:02:59,040 –> 00:03:01,519
بازه همدیگر را نمیپوشانند،
83
00:03:01,519 –> 00:03:03,360
اما راهحلی که من در مورد آن صحبت کردم
84
00:03:03,360 –> 00:03:04,480
85
00:03:04,480 –> 00:03:06,480
، n مربع خواهد بود، زیرا برای هر
86
00:03:06,480 –> 00:03:07,920
بازه، هر بازه دیگری را بررسی میکنیم و بررسی میکنیم که
87
00:03:07,920 –> 00:03:09,440
آیا وجود دارد یا خیر.
88
00:03:09,440 –> 00:03:11,599
اولی را پوشش میدهیم، اما آیا
89
00:03:11,599 –> 00:03:13,840
راه بهتری برای انجام آن وجود دارد، میتوانیم
90
00:03:13,840 –> 00:03:15,680
فواصل زمانی را به
91
00:03:15,680 –> 00:03:18,560
ترتیبی تکرار کنیم، جایی که شما میدانید در کجا
92
00:03:18,560 –> 00:03:20,000
مجبور نیستیم
93
00:03:20,000 –> 00:03:21,760
یک n مربع انجام دهیم، جایی که میتوانیم
94
00:03:21,760 –> 00:03:23,440
کل فهرست را
95
00:03:23,440 –> 00:03:26,560
یک بار به خوبی تکرار کنیم. اولین ایده من این است که آنها را
96
00:03:26,560 –> 00:03:29,360
بر اساس نقطه سمت چپ مرتب کنم، جایی که می
97
00:03:29,360 –> 00:03:31,120
دانید آنهایی که نقطه چپ کوچکتری دارند
98
00:03:31,120 –> 00:03:32,879
ابتدا می روند و سپس با یک
99
00:03:32,879 –> 00:03:34,720
نقطه چپ بزرگتر می روند دنبال
100
00:03:34,720 –> 00:03:36,959
دلیل این کار من این است که در این
101
00:03:36,959 –> 00:03:39,599
به عنوان مثال، این یکی دورترین
102
00:03:39,599 –> 00:03:41,840
نقطه چپ را دارد، هیچ چیز دیگری دارای یک
103
00:03:41,840 –> 00:03:44,000
نقطه چپ برابر یا نقطه چپ کوچکتر نیست،
104
00:03:44,000 –> 00:03:46,000
بنابراین آنچه در مورد این یکی می دانیم این است
105
00:03:46,000 –> 00:03:49,360
که احتمالاً نمی توان با هیچ یک از
106
00:03:49,360 –> 00:03:51,440
بازه های دیگر به سمت راست پوشانده شود، زیرا اگر
107
00:03:51,440 –> 00:03:53,760
این نقطه کوچک باشد. نقطه سمت چپ است پس مطمئناً
108
00:03:53,760 –> 00:03:55,200
توسط دیگری پوشانده نمی شود،
109
00:03:55,200 –> 00:03:56,799
بنابراین لازم نیست که به
110
00:03:56,799 –> 00:03:58,799
تک تک بازه ها نگاه کنیم تا بدانیم
111
00:03:58,799 –> 00:04:01,040
این یکی پوشش داده نمی شود، اما
112
00:04:01,040 –> 00:04:03,680
نگه دارید ممکن است فواصل دیگری وجود
113
00:04:03,680 –> 00:04:06,159
داشته باشند که همان نقطه سمت چپ را دارند. درست است، بنابراین
114
00:04:06,159 –> 00:04:08,239
فرض کنید بازه دیگری مانند
115
00:04:08,239 –> 00:04:10,720
این داشتیم که همان نقطه سمت چپ را دارد، اما
116
00:04:10,720 –> 00:04:12,640
شاید این یک نقطه سمت راست کوچکتر
117
00:04:12,640 –> 00:04:13,840
داشته باشد، زیرا به یاد داشته باشید که ما نمی توانیم تکراری داشته باشیم،
118
00:04:13,840 –> 00:04:15,920
بنابراین
119
00:04:15,920 –> 00:04:18,560
از بین این دو بازه، کدام یک
120
00:04:18,560 –> 00:04:21,040
را می خواهیم اول قرار دهیم،
121
00:04:21,040 –> 00:04:23,759
خوب ایده در اینجا این است که اولین مورد را
122
00:04:23,759 –> 00:04:25,680
طوری قرار دهیم که بدانیم
123
00:04:25,680 –> 00:04:27,680
اگر بخواهیم با کوچکترین نقاط چپ شروع کنیم نمی توان آن را به خوبی پوشش داد،
124
00:04:27,680 –> 00:04:29,600
اما
125
00:04:29,600 –> 00:04:31,680
اگر بین نقاط چپ تساوی وجود دارد،
126
00:04:31,680 –> 00:04:34,160
در واقع باید نقطه سمت راست را
127
00:04:34,160 –> 00:04:35,199
بزرگتر قرار دهیم.
128
00:04:35,199 –> 00:04:37,919
ابتدا به این دلیل اشاره کنید که اگر
129
00:04:37,919 –> 00:04:40,479
نقطه سمت راست بزرگتری داشته باشد، باید به این معنی باشد
130
00:04:40,479 –> 00:04:43,440
که با فواصل دیگری پوشانده نمی شود،
131
00:04:43,440 –> 00:04:45,759
زیرا اگر خوب تلاقی وجود داشته باشد، مقدار مناسب
132
00:04:45,759 –> 00:04:48,160
کوچکتر خواهد بود، بنابراین ما می دانیم که
133
00:04:48,160 –> 00:04:50,880
این نقطه پوشانده نمی شود، بنابراین
134
00:04:50,880 –> 00:04:52,880
ایده اینجاست که ما می روم برای مرتبسازی
135
00:04:52,880 –> 00:04:56,160
فواصل بر اساس کوچکترین نقطه چپ،
136
00:04:56,160 –> 00:04:58,320
اگر بین نقاط چپ تساوی وجود داشته باشد،
137
00:04:58,320 –> 00:05:00,400
میخواهیم فواصل را با
138
00:05:00,400 –> 00:05:02,240
نقطه سمت راست بزرگتر انجام دهیم، ابتدا
139
00:05:02,240 –> 00:05:03,680
بزرگترین
140
00:05:03,680 –> 00:05:06,560
فواصل را قرار میدهیم و سپس کوچکتر را قرار
141
00:05:06,560 –> 00:05:08,880
میدهیم، زیرا میدانیم فاصلههای بعد
142
00:05:08,880 –> 00:05:11,120
میتوانند پوشش داده شود اما اولین ها
143
00:05:11,120 –> 00:05:13,120
پوشش داده نخواهند شد، بنابراین ما
144
00:05:13,120 –> 00:05:15,039
با ورودی فواصل شروع می
145
00:05:15,039 –> 00:05:17,120
کنیم و همچنین خروجی
146
00:05:17,120 –> 00:05:18,880
فواصل را خواهیم داشت و کاری که می خواهیم انجام دهیم این است که
147
00:05:18,880 –> 00:05:20,639
اکنون از طریق آنها تکرار کنیم. ترتیبی
148
00:05:20,639 –> 00:05:22,160
که در مورد آن صحبت کردیم، این یکی
149
00:05:22,160 –> 00:05:23,600
ابتدا می رود زیرا کوچکترین
150
00:05:23,600 –> 00:05:25,919
نقطه سمت چپ را دارد و هیچ پیوندی وجود ندارد و
151
00:05:25,919 –> 00:05:27,840
ما فقط این را می گیریم و سپس
152
00:05:27,840 –> 00:05:30,880
آن را در خروجی قرار می دهیم و سپس به
153
00:05:30,880 –> 00:05:33,520
بازه بعدی با کوچکترین سمت چپ می رویم.
154
00:05:33,520 –> 00:05:35,360
نکته و فقط برای اینکه این موضوع جالب باشد،
155
00:05:35,360 –> 00:05:36,960
در واقع من قصد دارم چند
156
00:05:36,960 –> 00:05:39,680
مثال دیگر اضافه کنم، بیایید بگوییم
157
00:05:39,680 –> 00:05:43,840
این یکی و یک نمونه کوچکتر، بنابراین
158
00:05:43,840 –> 00:05:47,199
شاید چیزی شبیه به آن خوب باشد، پس حالا
159
00:05:47,199 –> 00:05:48,639
کدام یک از اینها را می خواهیم
160
00:05:48,639 –> 00:05:50,240
ابتدا نگاه کنید زیرا همه آنها یکسان هستند
161
00:05:50,240 –> 00:05:51,759
نقطه سمت چپ اما ما می خواهیم به
162
00:05:51,759 –> 00:05:54,080
نقطه ای با نقطه سمت راست بزرگتر نگاه کنیم تا این
163
00:05:54,080 –> 00:05:57,039
موردی که می خواهیم بگوییم می تواند به خروجی اضافه شود
164
00:05:57,039 –> 00:05:59,120
اما قبل از اینکه آن را به
165
00:05:59,120 –> 00:06:01,680
خروجی اضافه کنیم می دانیم که اگر چیزی قرار است
166
00:06:01,680 –> 00:06:03,919
این مورد را پوشش