Решении задачки

[lalala23]

помогите пожалуйста решить задачу в R.
условие:
Будем представлять посещение музея посетителем в виде отрезка [время_прихода_посетителя, время_ухода_посетителя]. Надо найти множество точек, принадлежащих максимальному числу отрезков (они и будут составлять тот промежуток (промежутки) времени, в течение которого в музее одновременно находилось максимальное число посетителей

[lalala23]

upppppppppppppp

[8Observer8]

Думаю решать задачу надо так:

- входные данные. В файле хранятся строки, в каждой строке записано время прихода и ухода посетителя.
- завести массив структур. Каждый элемент массива (структура) - это посетитель. В структуре следующие поля: время прихода, время ухода, количество пересечений с другими посетителями (счетчик), и обычный целочисленный массив номеров посетителей, с которыми пересекался данный посетитель.
- инициализировать массив структур из файла.
- взяв посетителя (структуру), сравнить с остальными на предмет пересечений временных отрезков (сравнивая времена приходов и уходов), фиксируя в счетчике пересечений этой структуры количество пересечений с другими посетителями. Необходимо фиксировать в целочисленном массиве номера посетителей, с которыми пересекался данный посетитель.
- повторить предыдущий пункт столько раз сколько у нас посетителей.
- выбрать посетителя у которого максимальное число пересечений.
- в структуре этого посетителя есть массив с номерами посетителей, с которыми от пересекался. Используя эти номера, отыскиваем посетителя с максимальным временем прихода. И так же отыскиваем посетителя с минимальным временем ухода. Разница и есть ответ.
- вот пожалуй и всё, мне так видится решение задачи.

P.S. У самого пока нет времени писать код. Попробуйте сами.

[stepler654]

Сообщение от 8Observer8

- в структуре этого посетителя есть массив с номерами посетителей, с которыми от пересекался. Используя эти номера, отыскиваем посетителя с максимальным временем прихода. И так же отыскиваем посетителя с минимальным временем ухода. Разница и есть ответ.

Неправильный алгоритм.
В музей пришел смотритель в 8.00 утра и ушел в 21.00.
Пенсионер пришел в 9 утра и ушел в 10 утра.
Днем в 13.00 пришло 40 японцев и все вместе ушли в 14.00
В 19.00 пришла студентка и ушла в 20.00.

Больше всего пересечений у смотрителя - 42.
Максимальное время прихода - у студентки (в 19.00)
Минимальное время ухода у пенсионера - 10.00

Очевидно, что масимальное число людей (41) находилось с 13.00 до 14.00.
Agreed?

[Rififi]

lalala23

Надо найти множество точек, принадлежащих максимальному числу отрезков (они и будут составлять тот промежуток (промежутки) времени, в течение которого в музее одновременно находилось максимальное число посетителей

На основе данных от stepler654

#include <iostream>
#include <locale>

#include <boost/icl/ptime.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/format.hpp>

#include <boost/assign/list_of.hpp>
using boost::assign::list_of;

template <typename Map>
void add(Map& map, const char* from, const char* to, const char* who)
{
	map.add(std::make_pair(
		typename Map::value_type::first_type::closed(
			boost::posix_time::duration_from_string(from),
			boost::posix_time::duration_from_string(to)),
			list_of(who).convert_to_container<typename Map::value_type::second_type>()
			));
}


int main()
{
	std::locale::global(std::locale(""));

	typedef boost::icl::interval_map<boost::posix_time::time_duration, std::set<std::string> > Map;
	Map museum;

	add(museum, "8:00", "21:00", "Смотритель");
	add(museum, "9:00", "10:00", "Пенсионер");

	for (size_t i = 0; i < 40; i++)
		add(museum, "13:00", "14:00", boost::str(boost::format("Японец#%1%") % i).c_str());

	add(museum, "19:00", "20:00", "Студентка");

	auto max = museum.begin();
	size_t max_visitors = 0;

	for (auto it = museum.begin(); it != museum.end(); ++it)
	{
		if (it->second.size() > max_visitors)
		{
			max_visitors = it->second.size();
			max = it;
		}
	}

	std::cout << "Максимальное количество посетителей (" << max_visitors << ") было в период: " << max->first << std::endl;
	
	return 0;
}